Repositorio Institucional de Documentos

Performance Bounds for Synchronized Queueing Networks Javier Campos Laclaustra Tesis Doctoral Departamento de Ingenier´ıa El´ectrica e Inform´atica Universidad de Zaragoza October 1990 i No es dado a todos aventurarse en la selva y trazar, a fuerza de energ´ıa, un camino practicable, pero aun los m´as humildes podemos aprovecharnos del sendero abierto por el genio, y arrancar, caminando por ´el, alg´un secreto a lo desconocido. Santiago Ram´ on y Cajal Los t´onicos de la voluntad, 1897 ii Contents List of figures vii List of tables xiii Preface xv Acknowledgements xix 1 Synchronized queueing networks and Petri nets 1 1.1 Queueing networks with synchronizations ......... 2 1.1.1 Monoclass queueing networks ........... 2 1.1.2 Addition of synchronization schemes ....... 6 1.2 Stochastic Petri nets .................... 8 1.2.1 Introducing nets .................. 9 1.2.2 Some terminology .................. 13 1.2.2.1 Net structure ............... 13 1.2.2.2 Token game ................ 14 1.2.2.3 Basic properties .............. 14 1.2.3 On stochastic Petri nets .............. 15 1.2.3.1 Timing and firing process ........ 15 1.2.3.2 Single versus multiple server semantics .17 1.2.3.3 Ergodicity and measurability ...... 20 1.3 Mapping between monoclass synchronized queueing networks and stochastic Petri nets .............. 26 1.4 Analytical techniques for synchronized queueing networks 28 1.5 An overview of performance bounds for stochastic Petri nets ............................. 33 iii iv CONTENTS 2 Petri net subclasses and bases of qualitative theory 37 2.1 FRT-nets and subclasses .................. 40 2.1.1 FRT-nets ...................... 41 2.1.1.1 Definition ................. 42 2.1.1.2 Algebraic characterization ........ 44 2.1.1.3 Qualitative properties .......... 51 2.1.2 Mono-T-semiflow, structurally decision-free nets, and marked graphs ................. 57 2.1.2.1 Mono-T-semiflow nets .......... 57 2.1.2.2 Structurally decision-free nets ...... 60 2.1.2.3 Marked graphs .............. 61 2.1.3 Free choice nets ................... 64 2.1.4 FRT-nets communicating through buffers ..... 69 2.1.4.1 Deterministic systems of sequential processes .................. 70 2.1.4.2 Totally open deterministic systems of sequential processes ........... 74 2.2 Persistent nets and behaviourally extended free choice nets 84 2.2.1 Persistent nets ................... 84 2.2.2 Behaviourally extended free choice nets ...... 88 2.3 Conclusions ......................... 89 3 Bounds for strongly connected marked graphs 91 3.1 Upper bound for the steady-state throughput ...... 94 3.1.1 Little’s law and P-semiflows ............ 94 3.1.2 Reachability of the upper bound .......... 98 3.1.3 Interpretation and derived results .........100 3.2 Lower bound for the steady-state throughput .......102 3.2.1 Basic result for 1–live marked graphs .......103 3.2.2 Extension to bounded marked graphs .......105 3.2.3 Reachability of the lower bound ..........109 3.2.4 A polynomial algorithm to compute the lower bound ........................111 3.3 Extending results to unbounded marked graphs .....113 3.4 Conclusions .........................120 CONTENTS v 4 Bounds for live and bounded free choice nets 123 4.1 Upper bounds for the steady-state throughput ......124 4.1.1 Little’s law and linear marking relations .....125 4.1.1.1 Structural linear marking relations ...126 4.1.1.2 Little’s law and P-semiflows .......127 4.1.1.3 Little’s law and traps ...........131 4.1.2 A new perspective: implicit places .........134 4.1.2.1 Implicit places ..............134 4.1.2.2 Reinterpretation of traps using implicit places .................. 136 4.1.2.3 Implicit places improve traps-based bounds .................. 138 4.1.3 Multisets of circuits: derivation of a reachable upper bound ....................142 4.2 Lower bounds for the steady-state throughput ......161 4.3 Conclusions .........................163 5 Extensions to other net subclasses 165 5.1 Mono-T-semiflow nets ...................165 5.1.1 Lower bound for the mean cycle time .......167 5.1.2 Upper bound for the mean cycle time .......171 5.2 FRT-nets ..........................173 5.2.1 Lower bound for the mean cycle time .......173 5.2.2 Upper bound for the mean cycle time .......175 5.3 Totally open deterministic systems of sequential processes176 5.3.1 Characterization of ergodicity ...........176 5.3.2 Computing the steady-state performance measures179 5.4 Persistent nets ........................181 5.4.1 Lower bound for the mean cycle time .......181 5.4.1.1 A reachable bound ............184 5.4.2 Upper bound for the mean cycle time .......185 5.5 Conclusions .........................186 6 Additional bounds and improvements 187 6.1 Bounds for other performance indexes ...........188 6.1.1 Bounds for the mean length of queues .......188 6.1.2 Maximum capacity of queues ...........190 vi CONTENTS 6.1.3 Other computable bounds .............191 6.2 Improving the bounds for Coxian timing .........191 6.2.1 Free choice case ...................192 6.2.2 Non-free choice case ................200 6.3 Conclusions .........................201 7 Applications to distributed systems 203 7.1 Distributed computing systems ..............203 7.1.1 The alternating bit protocol ............204 7.1.2 A software example .................205 7.1.3 The PADMAVATI architecture ..........211 7.1.4 A dataflow graph ..................216 7.2 Manufacturing systems ...................219 7.2.1 A job-shop system .................219 7.2.2 A kanban system ..................221 7.2.3 A producer-consumer system ...........225 Conclusions 229 Bibliography 235 List of Figures 1.1 A simple computer system with virtual memory. ..... 3 1.2 Queueing network model of a multiprogramming memory limited system. ..................... 7 1.3 Queueing network model of a fork/join multitasking process. ............................. 8 1.4 Typical schemes in the modelling of distributed systems. 10 1.5 Partial ordel formalism and temporal realism. ...... 11 1.6 A net with enabling bound greater than liveness bound for transition t1....................... 19 1.7 A trivial weakly but non-strongly marking ergodic deterministic net. ....................... 21 1.8 A net with home states but possibly non-ergodic marking process. ........................... 22 1.9 A live and bounded net without home states. ....... 23 1.10 Reachability graph of the net in figure 1.9 ........ 24 1.11 An example of stochastic Petri net representing a network of delay stations. ................... 26 1.12 A Petri net representation of a monoclass single-server queue. ............................ 27 1.13 A Petri net representation of a queueing network. .... 27 1.14 A more general stochastic net and the corresponding synchronized queueing network. ................ 29 1.15 Petri net model of a multiprogramming memory limited system. ........................... 30 1.16 Petri net model of a fork/join multitasking process. ... 30 1.17 Pathological cases of synchronized queueing networks. .. 31 vii viii LIST OF FIGURES 2.1 A net whose visit ratios depend on the structure, on the routing at conflicts, on the initial marking, and on the service times. ........................ 38 2.2 Inclusion relations among FRT-net subclasses (∗these are marked nets). ...................... 41 2.3 A live and structurally bounded FRT-net. ........ 44 2.4 Introduction of a local scheduler at an equality conflict set. .............................. 46 2.5 Counter-example to the converse of lemma 2.1.1. ..... 47 2.6 The addition of a token to p5kills the net (sequence σ=t4leads to a deadlock). ................ 53 2.7 Live and bounded FRT-net which is not structurally bounded. .......................... 54 2.8 A non-reversible live and structurally bounded FRT-net. 55 2.9 A live and structurally bounded FRT-net without home states. ............................ 56 2.10 A live and structurally bounded mono-T-semiflow net. .58 2.11 A deterministic system of sequential processes. ...... 71 2.12 Substitution of state machines by transitions in the net of figure 2.11. ........................ 73 2.13 A totally open deterministic system of sequential processes. 75 2.14 A non-consistent totally open deterministic system of sequential processes. .................... 77 2.15 Consistent totally open deterministic systems of sequential processes with two state machines and two buffers. .78 2.16 Structurally marking non-ergodic system with three state machines. ....................... 80 2.17 Regulation circuits between transitions in global synchronic distance relation. .................. 82 2.18 Persistent net. ........................ 85 2.19 Persistent and non-persistent nets with the same structure. 86 2.20 An unbounded live persistent net having the directedness property but without home states. ............ 87 2.21 Structurally persistent but non-structurally decision-free net. ............................. 89 Preface Product form queueing networks have long been used for the performance evaluation of computer systems. Their success has been due to their capability of naturally expressing sharing of resources and queueing, that are typical situations of traditional computer systems, as well as to their efficient solution algorithms, of polynomial complexity on the size of the model. Unfortunately, the introduction of synchronization constraints usually destroys the product form solution, so that general concurrent and distributed systems are not easily studied with this class of models. Petri nets have been proved specially adequate to model parallel and distributed systems. Moreover, they have a well-founded theory of analysis that allows to investigate a great number of qualitative properties of the system. In the original definition, Petri nets did not include the notion of time, and tried to model only the logical behaviour of systems by describing the causal relations existing among events. This approach showed its power in the specification and analysis of concurrent systems in a way independent of the concept of time. Nevertheless the introduction of a timing specification is essential if we want to use this class of models for the performance evaluation of distributed systems. One of the main problems in the actual use of timed and stochastic Petri net models for the quantitative evaluation of large systems is the explosion of the computational complexity of the analysis algorithms. In general, exact performance results are obtained from the numerical solution of a continuous time Markov chain, whose dimension is given by the size of the state space of the model. Structural computation of exact performance measures has been possible for some subclasses of nets such as those with state machine topology. These nets, under xv xvi PREFACE certain assumptions on the stochastic interpretation are isomorphic to Gordon and Newell’s networks, in queueing theory terminology. In the general case, efficient methods for the derivation of performance measures are still needed. Two complementary approaches to the derivation of exact measures for the analysis of distributed systems are the utilization of approximation techniques and the computation of bounds. Approximate values for the performance parameters are in general more efficiently derived than the exact ones. On the other hand, “exactness” only exists in theory! In other words, numerical algorithms must be applied in practice for the computation of exact values, therefore making errors is inevitable. Performance bounds are useful in the preliminary phases of the design of a system, in which many parameters are not known accurately. Several alternatives for those parameters should be quickly evaluated, and rejected those that are clearly bad. Exact (and even approximate) solutions would be computationally very expensive. Bounds become useful in these instances since they usually require much less computation effort. The computation of upper and lower bounds for the steady-state performance of timed and stochastic Petri nets is considered in this work. In particular, we study the throughput of transitions, defined as the average number of firings per time unit. For this measure we try to compute upper and lower bounds in polynomial time on the size of the net model, by means of proper linear programming problems defined from the incidence matrix of the net (in this sense, we develop structural techniques). These bounds depend only on the mean values and not on the higher moments of the probability distribution functions of the random variables that describe the timing of the system. The independence of the probability distributions can be viewed as a useful generalization of the performance results, since higher moments of the delays are usually unknown for real cases, and difficult to estimate and assess. From a different perspective, the obtained results can be applied to the analysis of queueing networks extended with some synchronization schemes. Monoclass queueing networks can be mapped on stochastic Petri nets. On the other hand, stochastic Petri nets can be interpreted PREFACE xvii as monoclass queueing networks augmented with synchronization primitives. Concerning the presentation of this manuscript, it should be mentioned that chapter 1 has been written with the object of giving the reader an outline of the stochastic Petri net model: its definition, terminology, basic properties, and related concepts, together with its deep relation with other classic stochastic network models. Chapter 2 is devoted to the presentation of the net subclasses considered in the rest of the work. The classification presented here is quite different from the one which is usual in the framework of Petri nets. The reason lies on the fact that our classification criterion, the computability of visit ratios for transitions, is introduced for the first time in the field of stochastic Petri nets in this work. The significance of that criterion is based on the important role that the visit ratios play in the computation of upper and lower bounds for the performance of the models. Nevertheless, classical important net subclasses are identified here in terms of the computability of their visit ratios from different parameters of the model. Chapter 3 is concerned with the computation of reachable upper and lower bounds for the most restrictive subclass of those presented in chapter 2: marked graphs. The explanation of this fact is easy to understand. The more simple is the model the more accessible will be the techniques an ideas for the development of good results. Chapter 4 provides a generalization for live and bounded free choice nets of the results presented in the previous chapter. Quality of obtained bounds is similar to that for strongly connected marked graphs: throughput lower bounds are reachable for bounded nets while upper bounds are reachable for 1–bounded nets. Chapter 5 considers the extension to other net subclasses, like monoT-semiflow nets, FRT-nets, totally open deterministic systems of sequential processes, and persistent nets. The results are of diverse colours. For mono-T-semiflow nets and, therefore, for general FRTnets, it is not possible (so far) to obtain reachable throughput bounds. On the other hand, for bounded ordinary persistent nets, tight throughput upper bounds are derived. Moreover, in the case of totally open deterministic systems of sequential processes the exact steady-state performance measures can be computed in polynomial time on the net size. xviii PREFACE In chapter 6 bounds for other interesting performance measures are derived from throughput bounds and from classical queueing theory laws. After that, we explore the introduction of more information from the probability distribution functions of service times in order to improve the bounds. In particular, for Coxian service delay of transitions it is possible to improve the throughput upper bounds of previous chapters which held for more general forms of distribution functions. This improvement shows to be specially fruitful for live and bounded free choice nets. Chapter 7 is devoted to case studies. Several examples taken from literature in the fields of distributed computing systems and manufacturing systems are modelled by means of stochastic Petri nets and evaluated using the techniques developed in previous chapters. Finally, some concluding remarks and considerations on possible extensions of the work are presented. Acknowledgements It is a pleasure to acknowledge a few of my debts. Like all Spanish Petri nets’ researchers, I owe everything to Manuel Silva; friend, colleague, and advisor of this thesis, to whom go my foremost thanks, for his constant guidance and help. I would also like to thank Miguel San Miguel, who first aroused my interest in applied stochastic processes and queueing theory. I must say how grateful I am to all the colleagues of the Grupo de Ingenier´ıa de Sistemas e Inform´atica of the Universidad de Zaragoza, and especially to Jos´e Manuel Colom, who has offered constructive comments and discussions during the past years. Other persons have contributed to the derivation of the results presented in this manuscript. Special thanks go to Giovanni Chiola, for his fruitful cooperation. Finally, to my family and friends. I am eternally grateful for their patience and support. Javier Campos Zaragoza, October 1990. xix xx ACKNOWLEDGEMENTS Chapter 1 Synchronized queueing networks and Petri nets Queueing network models are one of the most popular and classical tools for the performance evaluation of computer systems. With the advent of complex distributed systems, many proposals have been made to extend the modelling power of queueing networks by adding various synchronization mechanisms to the basic model. One of the most important characteristics of basic queueing networks that determined their popularity was the development of efficient (polynomial complexity) algorithms, based on their “product form solution”. Unfortunately, the introduction of synchronization mechanisms usually destroys this nice property. More recently, timed and/or stochastic Petri net models have been introduced as a modelling tool capable of naturally represent synchronization and concurrency. The intimate relation between synchronized queueing networks and stochastic Petri nets is stressed in this chapter. After an historical route through the main hits of queueing networks theory, we justify the necessity of the introduction of synchronization schemes for the performance evaluation of distributed systems. Then, we formally introduce the model of Petri nets, as well as the different implications that the addition of a timing interpretation has in the model. Finally, the close relations between queueing networks with synchronization constraints and stochastic Petri nets are remarked. 1 2CHAPTER 1. Synchronized queueing networks and Petri nets 1.1 Queueing networks with synchronizations Queueing network models have been used for performance evaluation since the early work of A. Erlang [Erl09]. Their success for the analysis of computer systems (see, e.g., [Kle76,LZGS84,Lav89]) has been due to their capability of naturally expressing sharing of resources and queueing, that are typical situations of traditional computer systems, as well as to their efficient solution algorithms, of polynomial complexity on the size of the model. 1.1.1 Monoclass queueing networks A queueing network model of a system is a collection of service centers or stations and customers moving among them. The service centers represent different processing sites while customers represent jobs or processes. Customers can enter the system at certain points; after that they move from one station to another, queueing up at each for some service; and ocassionally they depart from the system. More formally, a queueing network is a trio SC,R,X 0, where •SC={1,...,m}is the set of service centers, •Ris the real matrix of routing probabilities rij ≥0; i, j =1,...,m; where rij is the probability that a customer exiting center igoes to j, and •X0is the vector of external arrival rates X0i≥0, i=1,...,m, to stations. If X0i= 0 for all station i, the number of customers in the network remains constant, it is denoted as N, and the system is called closed network. Otherwise, the network is said to be open. A queueing network can be seen as a directed graph in which service centers are the nodes. An arc from node ito node jis drawn iff rij > 0. As an example, see the closed network depicted in figure 1.1, that models a simple computer system with virtual memory [GP87]. In this CPU memory disc ρ 1 ρ 2 ρ 3 s12 3 s s 1.1. Queueing networks with synchronizations 3 Figure 1.1: A simple computer system with virtual memory. case, if CPU,memory, and disc are labelled with indexes 1,2, and 3, respectively, we have R=⎛ ⎜ ⎝ ρ1ρ2ρ3 100 100 ⎞ ⎟ ⎠(1.1) In fact, since each node in the system is a service center with a storage room for queues to form, a queueing network can be seen also as a bipartite directed graph. Service centers and storage rooms are the two kinds of nodes. An arc exists from each storage room to its corresponding service center. Finally, an arc from the service center i to the storage room preceding center jis drawn iff rij >0. The state of the network is defined by a vector n =(n1,...,n m)T, where niis the number of customers at center i(including those being served and those waiting). In order to completely define the model, the queueing disciplines at each of the storage rooms, the intensity of arrivals from outside, the service requirements of jobs at centers, and specially the average service time siof each station imust be specified. When all the above parameters are “appropriately” defined the evolution of the system can be modelled by a continuous time Markov chain [Rev84]. In this case the limit, or stationary, state distribution can be found, if it exists, by solving a system of linear equations, called global balance equations, which, for each state, equates the rate of flow into to the rate of flow out of the state. Unfortunately, the number of states (and therefore the dimension of the system of equations) increases quickly when the number of customers and stations grows. 4CHAPTER 1. Synchronized queueing networks and Petri nets The following system of equations [Kle75] can be derived from the global balance property: X(j)=X0j+ m  i=1 X(i)rij j=1,...,m (1.2) where X(i) is the limit throughput of station i, i.e., the average number of service completions per unit time at station i. If the network is open (i.e., if there exists a station jwith positive external arrival rate, X0j>0), then the above mequations are linearly independent, and the exact throughputs of stations can be derived (independently of the service times). This is not the case for closed networks. If X0j=0,j=1,...,m, then only m−1 equations are linearly independent, and thus only ratios of throughputs can be determined. These relative throughputs which are often called visit ratios, denoted as vifor each station i, summarize all the information given by the routing probabilities that is necessary in most cases for the computation of the performance measures. The visit ratios normalized, for instance, for station 1 are defined as: v(1) i def =X(i) X(1) i=1,...,m (1.3) For a restricted class of networks, called product form networks, the solution to the global balance equations can be shown to be a product of terms, one for each station, where the form of each term is explicitly given. This fact occurs when the system satisfies the local balance equations [Cha72]. Informally, a local balance equation asserts that for any two adjacent states the effective flow from one to the other must be equal to the effective flow in the other direction. J. Jackson [Jac63] found the first product form solution in a general network of queues, motivated by manufacturing applications. J. Jackson considered open monoclass networks with a Markovian arrival process dependent on the total population of the network. Service disciplines are FCFS (first-come first-served) and service times are exponential (with queue length dependent rates). W. Gordon and G. Newell [GN67] extended Jackson’s results to cover closed networks. The steady-state probability p(n) of state n =(n1,...,n m)Tin a p1 p2p3 p5 p4 t1 t2t3 t4 p2p5 p3p4 p2p3 p4p5 p1 t1 t2t3 t2 t3 t4 s + max (s ,s ) + s ≠ 1234 s + s + s + s 1234 1.2. Stochastic Petri nets 11 Figure 1.5: Partial ordel formalism and temporal realism. (see figure 1.4). In this direction, Petri nets improve clearly the modelling power of classic queueing networks, for which synchronizations are difficult or impossible to express, except for some extended formalisms (see section 1.1.2). One aspect of the adequacy of Petri net models is their possibility of expressing all basic semantics of concurrency, interleaving,step, and partial order semantics, which can be compared within the Petri net formalism. In this sense, Petri nets are capable of modelling “true concurrency”. The importance of true concurrency in a performance oriented concurrent model can be explained from the temporal realism that provides step and partial order semantics of concurrent events. Let us briefly describe these considerations with the use of the net depicted in figure 1.5. Activities modelled with transitions t2and t3 are truly concurrent. This means that the completion time of both is max{γ2,γ 3}if γ2and γ3are their respective random service times, and not γ2+γ3that would be obtained with interleaving semantics (and could be thought at first glance from a direct interpretation of the reachability graph, which represents a complete sequentialization of the behaviour of the model). Locality of states and actions constitutes another aspect of adequacy 12 CHAPTER 1. Synchronized queueing networks and Petri nets for the modelling of concurrent systems. It provides the possibility of progressive modelling by using stepwise refinements (top-down) or modular composition (bottom-up modelling). As in the case of queueing network models, the graphical representation of Petri nets is being crucial for the increasing interest of systems designers in this model. However, distributed and concurrent systems are complex and difficult to master for designers by nature. Therefore, desirable “good properties” must be formally defined and the model must be validated for these properties. In this sense, qualitative analysis of Petri nets is important before going on the implementation. A wide range of techniques for checking synchronic (lead,distance,places bounds,places mutual exclusions...) and activity properties (deadlockfreeness,liveness,home states. . . ) are reasonably known. Reachability analysis, based on the construction of the state space of the model, provides a complete knowledge of all its properties if the net is bounded (i.e., if the number of reachable states is finite). However, the exponencial temporal and spatial computational complexity originated from the state explosion reduces the applicability of this enumeration technique. In order to avoid the state explosion, reduction/transformation and structural techniques have been developed. The first are based on the application of local rules for the simplification of nets, preserving some of the desirable properties. On the other hand, structural techniques allow to conclude about some properties of the model just from the net structure and using mathematical tools taken from graph theory,linear algebra,convex geometry,orlinear programming. Regarding quantitative analysis of Petri nets with timing interpretation, the most commonly used technique consists on the derivation of exact performance measures from the reachability graph of the model (if bounded) which is identified with a Markov chain, under certain assumptions on the stochastic specification. As in the case of qualitative reachability analysis, the explosion of the computational complexity is the main problem in the actual use of this technique for the performance evaluation of large models. Alternative methods for the quantitative evaluation of Petri net models have been tried out. As in the case of queueing networks, approximation techniques and the computation of bounds constitute an 1.2. Stochastic Petri nets 13 option instead of exact analysis. The study of the second one has been our choice! 1.2.2 Some terminology The purpose of this section is just to introduce some notations and terminology to be extensively used in the sequel. The reader is assumed to be familiar with basic Petri nets concepts. 1.2.2.1 Net structure A Petri net is a 4-tuple N=P, T, Pre, Post, where •Pis the set of places (|P|=n), •Tis the set of transitions (|T|=m,P∩T=∅,P∪T=∅), •Pre(Post) is the pre- (post-) incidence function representing the input (output) arcs, Pre:P×T→IN = {0,1,2,...}(Post:P× T→IN). A Petri net can be seen as a bipartite directed graph in which places and transitions are the two kinds of nodes. Places are usually drawn as circles while transitions are depicted as bars or boxes. Ordinary nets are Petri nets whose pre and post incidence functions take values in {0,1}. The incidence function of a given arc in nonordinary nets is called weight or multiplicity. The preand post-sets of a transition t∈Tare defined respectively as •t={p|Pre(p, t)>0}and t•={p|Post(p, t)>0}. The preand post-sets of a place p∈Pare defined respectively as •p={t|Post(p, t)>0}and p•={t|Pre(p, t)>0}. The incidence matrix of the net C=[cij], i=1,...,n,j=1,...,m, is defined by cij =Post(pi,t j)−Pre(pi,t j). Similarly the preand post-incidence matrices are defined as PRE =[aij] and POST =[bij], where aij =Pre(pi,t j) and bij =Post(pi,t j). 14 CHAPTER 1. Synchronized queueing networks and Petri nets 1.2.2.2 Token game A function M:P→IN (usually represented in vector form) is called marking.Amarked Petri net N ,M 0is a Petri net Nwith an initial marking M0. A transition t∈Tis enabled at marking Miff ∀p∈P:M(p)≥ Pre(p, t). A transition tenabled at Mcan fire yielding a new marking M(reached marking) defined by M(p)=M(p)−Pre(p, t)+Post(p, t) (it is denoted by M[tM). A sequence of transitions σ=t1t2...tnis a firing sequence of N,M 0iff there exists a sequence of markings such that M0[t1M1[t2 M2...[tnMn. In this case, marking Mnis said to be reachable from M0 by firing σ, and this is denoted by M0[σMn. Expresion M[σdenotes a firable sequence σfrom marking M. The function σ:T→IN is the firing count vector or Parikh vector [Par66] of the firable sequence σ, i.e., σ[t] represents the number of occurrences of t∈Tin σ.IfM0[σM, then we can write in vector form M=M0+C·σ, which is referred to as the linear state equation of the net. A marking Mis said to be potentially reachable iff ∃ X≥0 such that M=M0+C· X≥0. 1.2.2.3 Basic properties The reachability set R(N,M 0) is the set of all markings reachable from the initial marking. Denoting by PR(N,M 0) the set of all potentially reachable markings we have the following relation: R(N,M 0)⊆ PR(N,M 0). L(N,M 0) is the set of all firing sequences and their suffixes in N,M 0:L(N,M 0)={σ|M[σwith M∈R(N,M 0)}. A place p∈Pis said to be k–bounded iff ∀M∈R(N,M 0), M(p)≤ k. A marked net N,M 0is said to be (marking) k–bounded iff each of its places is k–bounded. A net Nis structurally bounded iff ∀M0the marked nets N ,M 0are k–bounded for some k∈IN . Given an initial marking, an implicit place is one which never is the unique that restricts the firing of its output transitions. Let Nbe any net and Npbe the net resulting from adding an implicit place pto N. Therefore, the firing sequences in N,M 0and Np,Mp 0are identical. A transition t∈Tis live in N,M 0iff ∀M∈R(N,M 0): ∃M∈ R(N,M) such that Menables t. The marked net N,M 0is live iff all 1.2. Stochastic Petri nets 15 its transitions are live (i.e., liveness of the net guarantees the possibility of an infinite activity of all transitions). A net Nis structurally live iff ∃M0such that the marked net N ,M 0is live. The marked net N,M 0 is deadlock-free iff ∀M∈R(N,M 0): ∃t∈Tsuch that Menables t.A marked net has a total deadlock iff it is not deadlock-free. Aconsistent component (or T-semiflow ) is a function (vector) X:T→IN such that X= 0 and C·X=0. Aconservative component (or P-semiflow ) is a function (vector) Y:P→IN such that Y= 0 and YT·C= 0. The support of (Tand P-) semiflows is defined by ||X|| ={t∈T|X(t)>0}and ||Y|| ={p∈P|Y(p)>0}. A (Tor P-) semiflow Ihas minimal support iff there exist no other semiflow Isuch that ||I|| ⊂ ||I||. A (Tor P-) semiflow is canonical iff the greatest common divisor of its components is 1. A (Tor P-) semiflow is elementary iff it is canonical and has minimal support. A net Nis consistent iff there exists a T-semiflow X≥11. A net Nis conservative iff there exists a P-semiflow Y≥11. M∈R(N,M 0)isahome state iff ∀M∈R(N,M 0):M∈ R(N,M). M∈R(N,M 0)isatransient state iff it is not a home state. A marked net is reversible iff its initial marking is a home state. 1.2.3 On stochastic Petri nets In the original definition, Petri nets did not include the notion of time, and tried to model only the logical behaviour of systems by describing the causal relations existing among events. This approach showed its power in the specification and analysis of concurrent systems in a non-interleaved way, independent of the concept of time. Nevertheless the introduction of timing specification is essential if we want to use this class of models for an evaluation of the performance of distributed systems [TPN85,PNPM87,PNPM89]. 1.2.3.1 Timing and firing process Since Petri nets are bipartite graphs, historically there have been two ways of introducing the concept of time in them, namely, associating a time interpretation (deterministic or stochastic) with either places [Sif78] or transitions [Ram74]. Since transitions represent activities that 16 CHAPTER 1. Synchronized queueing networks and Petri nets change the state (marking) of the net, it seems natural to associate a duration with these activities (transitions). The latter has been our choice. In other words, from a queueing theory perspective, the service stations are represented by timed transitions, and we denote by sithe average service time of transition ti. In the case of timed transition models, two different firing rules have been defined: 1) “timed firing” of transitions in three phases which changes the firing rule of Petri nets introducing a timed phase in which the transition is “working” after having removed tokens from the input and before adding tokens to the output places, or a 2) “timed enabling” followed by an atomic firing which does not affect the usual Petri net firing rule. These different timing interpretations have different implications on the resolution of conflicts [AMBB+89]. On the one hand, using timed transition models with three phases firing we can define a policy for conflict resolution independent of the time specification but we cannot model pre-emption. On the other hand, using timed transition models with single phase firing we can model pre-emption but we cannot define conflict resolution policies independent of the timing specification (the conflicts are usually resolved in this case with race policy, i.e., the transition which samples the minimum service time is the one whose firing determines the change of marking). In order to avoid the coupling between resolution of conflicts and duration of activities, we suppose that transitions in conflict are immediate (they fire in zero time). Decisions at these conflicts are taken according to routing rates associated with immediate transitions (generalized stochastic Petri nets [AMBC84,AMBCC87a]). In this way, preemption cannot be modelled. In other words, each subset of transitions {t1,...,t k}⊂Tthat are in conflict in one or several reachable markings are considered immediate, and the constants r1,...,r k∈IN +are explicitly defined in the net interpretation in such a way that when t1,...,t kare enabled, transition ti(i=1,...,k) fires with probability (or with long run rate, in the case of deterministic conflicts resolution policy) ri/(k j=1 rj). Note that the routing rates are assumed to be 1.2. Stochastic Petri nets 17 strictly positive, i.e., all possible outcomes of any conflict have a nonnull probability of firing. This fact guarantees a fair behaviour for the non-autonomous Petri nets that we consider (a marked net is said to be fair iff all transitions that are simultaneously enabled infinitely many times will fire infinitely often). In summary, we model service stations by means of (deterministic or stochastic) timed transitions, routing by means of immediate transitions in conflict, and both kinds of transitions, timed and immediate, can be used as fork (split) nodes and join (synchronization) nodes. 1.2.3.2 Single versus multiple server semantics Another possible source of confusion in the definition of the timed interpretation of a Petri net model is the concept of degree of enabling of a transition (or re-entrance). In the case of timing associated with places, it seems quite natural to define an unavailability time which is independent of the total number of tokens already present in the place, an this can be interpreted as an infinite-server policy from the point of view of queueing theory. In the case of time associated with transitions, it is less obvious a-priori whether a transition enabled ktimes in a marking should work at conditional speed 1 or ktimes that it would work in the case it was enabled only once. In the case of stochastic Petri nets with exponentially distributed service times associated with transitions, the usual implicit hypothesis is to have single-server semantics (see, e.g., [Mol82,FN85a]), and the case of multiple-server is handled as a case of service rate dependent on the marking; this trick cannot work in the case of more general probability distributions. This is the reason why people working with deterministic timed transitions Petri nets prefer an infinite-server semantics (see, e.g., [RP84,HV85,Zub85]). Of course an infinite-server transition can always be constrained to a “k–server” behaviour by adding one place that is both input and output (self-loop with multiplicity 1) for that transition and marking it with ktokens. Therefore, the infinite-server semantics appears to be the most general one, and for this reason it is adopted in this work. The maximum number of servers working in parallel at a given transition will be characterized with the enabling bound concept. 18 CHAPTER 1. Synchronized queueing networks and Petri nets Definition 1.2.1 (Enabling bound) Let N ,M 0be a marked Petri net. The enabling bound of a given transition tof Nis E(t)def = max{k|∃M∈R(N,M 0): M≥kPRE[t]} Since in this work we are interested in the steady-state performance of a model, one can ask the question how many servers are available in transitions in steady-state condition. The answer is the definition of the liveness bound concept. Definition 1.2.2 (Liveness bound) Let N,M 0be a marked Petri net. The liveness bound of a given transition tof Nis: L(t)def = max{k|∀M∈R(N,M 0),∃M∈R(N,M): M≥kPRE[t]} The above definitions allow to generalize the classical concepts of enabling and liveness of a transition. In particular, a transition tis live if and only if L(t)>0, i.e., if there is at least one working server associated with it in steady-state conditions. The following is also obvious from the definitions. Property 1.2.1 Let N,M 0be a marked Petri net, then for all transition tof N,E(t)≥L(t). A case of strict inequality in this property can be interpreted as a generalization of the concept of non-liveness: there exist transitions containing “potential servers” that are never used in the steady-state; these additional servers might only be used in a transient phase, so they “die” during the evolution of the model. See, as an example, the net in figure 1.6. For transition t1we have: E(t1)=2>L(t1)=1. Since for any reversible net (i.e., such that M0is a home state) the reachability graph (which is a directed labelled graph with the reachable markings as nodes) is strongly connected, the following can be stated: Property 1.2.2 Let N,M 0be a reversible marked Petri net, then for all transition tof N,E(t)=L(t). t 2 p11t2 t3 p2 p3 1.2. Stochastic Petri nets 19 Figure 1.6: A net with enabling bound greater than liveness bound for transition t1. The definition of enabling bound refers to a behavioural property that depends on the reachability graph of a Petri net. Since we are looking for computational techniques at the structural level, we can also introduce the structural counterpart of the enabling bound concept. Structural net theory has been developed from two complementary points of view: graph theory [Bes87] and mathematical programming (or more specifically linear programming and linear algebra) [SC88]. Let us introduce our structural definition from the mathematical programming point of view; essentially in this case the reachability condition is substituted by the (in general) weaker (linear) constraint that markings satisfy the net state equation: M=M0+C·σ, with M,σ≥0. Definition 1.2.3 (Structural enabling bound) Let Nbe a Petri net. The structural enabling bound of a given transition tof Nis SE(t)def =maximize k subject to M=M0+C·σ ≥kPRE[t] σ ≥0 (LPP1) Note that the definition of structural enabling bound reduces to the formulation of a linear programming problem [Mur83]. Now let us remark the relation between behavioural and structural enabling bound concepts that follows from the implication “M∈ R(N,M 0)⇒M=M0+C·σ ∧σ ≥0”. Property 1.2.3 Let N,M 0be a marked Petri net, then for all transition tof N,SE(t)≥E(t). 20 CHAPTER 1. Synchronized queueing networks and Petri nets 1.2.3.3 Ergodicity and measurability In order to compute the steady-state performance of a system we have to assume that some kind of “average behaviour” can be estimated on the long run of the system we are studying. The usual assumption in this case is that the system model must be ergodic [Ros83], meaning that at the limit when the observation period tends to infinity, the estimates of average values tend (almost surely) to the theoretical expected values of the (usually unknown) probability distribution functions that characterize the performance indexes of interest. This assumption is very strong and difficult to verify in general; moreover, it creates problems when we want to include the deterministic case as a special case of a stochastic model, since the existence of the theoretical limiting expected value can be hampered by the periodicity of the model. Thus we introduce the concept of weak ergodicity that allows the estimation of long run performance also in the case of deterministic models. Definition 1.2.4 (Weak and strong ergodicities) 1. A (not necessarily stochastic) process Zτ, where τ≥0represents the time, is said to be weakly ergodic (or measurable in long run) iff the following limit exists: lim τ→∞ 1 ττ 0Zudu < ∞(1.7) 2. A stochastic process Zτ, where τ≥0represents the time, is said to be (strongly) ergodic iff the following condition holds: lim τ→∞ 1 ττ 0Zudu = lim τ→∞ E[Zτ]<∞(a.s.) (1.8) For stochastic Petri nets, weak ergodicity of the marking and the firing processes can be defined in the following terms: Definition 1.2.5 (Weak ergodicity of marking and firing) The marking process Mτ, where τ≥0represents the time, of a stochastic marked net is weakly ergodic iff the following limit exists: Mdef = lim τ→∞ 1 ττ 0Mudu < ∞(1.9) q s t e q1 t1 q2 q3 t2 t3 e1 s2 s3 r12 r13 1.3. Mapping between synchronized QNs and stochastic PNs 27 Figure 1.12: A Petri net representation of a monoclass single-server queue. Figure 1.13: A Petri net representation of a queueing network. 28 CHAPTER 1. Synchronized queueing networks and Petri nets transitions model the service times. On the other hand, stochastic nets can assume forms much more complex than the one illustrated in the example of figure 1.13. Figure 1.14 illustrates a more general stochastic Petri net that cannot be mapped onto a product form queueing network. In fact, this net can be mapped on an extended queueing network [SMK82], in which such constructs as fork, join, and passive resources are used to map the effect of the pairs of transitions t2–t7and t9–t10, respectively. These examples show how, using a Petri net formalism, extensions of product form queueing networks are represented with an analogous level of structural complexity of BCMP networks. In section 1.1, extended queueing network models were presented for the modelling of a multiprogramming memory limited system (figure 1.2) and a fork/join multitasking process (figure 1.3). The corresponding Petri net models are depicted in figures 1.15 and 1.16, respectively. The reader is noticed that “unclever” use of synchronizations in queueing networks can lead to pathological cases as unbounded number of customers or total deadlock (see figure 1.17), that need to be carefully studied. Finally, let us remark that stochastic Petri nets with weighted arcs (i.e., non-ordinary nets) can be used for the modelling of bulk arrivals and bulk services [Kle75], with deterministic size of batches (given by the weights of arcs). As an example, transition t3of Petri net in figure 1.6 is a bulk service system which accepts a batch of exactly two tokens (customers) from the place p3, and serves them collectively. 1.4 Analytical techniques for synchronized queueing networks One of the main problems in the actual use of timed and stochastic Petri net models for the performance evaluation of large systems is the explosion of the computational complexity of the analysis algorithms. In general, exact performance results are obtained from the numerical solution of a continuous time Markov chain [BT81,Mol81,FN85b]. This exact computation is only possible for bounded nets (finite state space), (a) Stochastic Petri net representation. (b) Extended queueing network representation. FJ R AF 1 R 2 A J C=3 C t1 t2 t3 t4 t5 t6t7 t8 t9t10 1.4. Analytical techniques for synchronized QNs 29 Figure 1.14: A more general stochastic net and the corresponding synchronized queueing network. C M terminals memory queue processor I/O devices memory partitions 30 CHAPTER 1. Synchronized queueing networks and Petri nets Figure 1.15: Petri net model of a multiprogramming memory limited system. Figure 1.16: Petri net model of a fork/join multitasking process. F (a) A total deadlock will be reached sooner or later, even for q =1/2. (b) Any infinite behaviour will lead to an infinite number of customers. JF FJ 1-q q 1.4. Analytical techniques for synchronized QNs 31 Figure 1.17: Pathological cases of synchronized queueing networks. and under exponential assumption for the service time of transitions. And the worst of it is that the dimension of the state space of the embedded Markov chain grows exponentially with the net size. The same problem arose in the framework of queueing networks before the work of J. Jackson, and it was solved by means of the introduction of product form equations [Jac63,GN67,BCMP75], and efficient algorithms for their solution [Buz73,RK75,RL80,BB80]. Unfortunately, the generalization of these results to more complex stochastic models with synchronization features seems to be very difficult, and a very few number of results have been already published. Related with open networks, a matrix product form solution is known only for stochastic Petri nets with at most one place unbounded [FN86]. In [FN89a], G. Florin and S. Natkin presented the first general product form expresion in matrix form for closed (i.e., bounded) ordinary stochastic Petri nets with strongly connected reachability graph. The great difference between scalar (Gordon-Newell result for closed queueing networks) and matrix product forms appears in numerical computation. Solving synchronized queueing networks implies much 32 CHAPTER 1. Synchronized queueing networks and Petri nets more complex algorithms than classical ones. The problem of computing the normalization constant in the scalar product form solution is replaced by the computation of a constant vector obtained solving a system of linear equations, which is ill-conditioned. This is the reason why the paper of Florin and Natkin can be considered mainly of theoretical significance. Other works dealing with this problem [AMBCD86,LR87] consider only very restrictive subclasses of Petri nets. Therefore, efficient computational methods are still needed. Approximation techniques have been developed in the framework of non-product form queueing networks for overcoming the practical limitations of exact solutions. The “flow equivalent” server decomposition method is probably the most used in practice [Lav89]. In this method, a subnetwork is replaced by a server with exponentially distributed service times and queue length dependent service rates. The rates are obtained by solving the throughput of the isolated subnetwork once for each possible value of number of customers in the subnetwork. The aggregated system consisting of this flow equivalent server and the rest of the original network is then solved. Two different theoretical justifications for the fitness of the flow equivalent server method can be given. The first is that it yields exact results for single chain product form networks [CHW75]. This result is called Norton’s theorem for product form queueing networks due to its analogy with Norton’s theorem for electrical circuits (in which a subsystem is replaced by a current source and parallel resistance that are equivalent to the original subsystem in terms of their effect on the rest of the system). This exact result for product form queueing networks suggests that the flow equivalent server method may yield fairly accurate approximations for networks that are “almost product form”. The second justification for the use of this method was performed by P. Courtois [Cou77] within the framework of the computation of the steady-state solution of large Markov chains in which states are aggregated into macrostates to reduce the computational complexity of the solution (nearly or completely decomposable systems). Practical experience shows that using decomposition techniques for the solution of non-product form networks made up of subsystems that, taken in isolation, satisfy the product form conditions often yields quite 1.4. Performance bounds for stochastic PNs 33 acceptable results [AMBC86]. A complementary approach to the approximation techniques for the analysis of queueing networks is the computation of bounds. Performance bounds are useful in the preliminary phases of the design of a system, in which many parameters are not known accurately. Several alternatives for those parameters should be quickly evaluated, and rejected those that are clearly bad. Exact (and even approximate) solutions would be computationally very expensive. Bounds become useful in these instances since they usually require much less computation effort. A large number of bounding techniques have been proposed for the performance measures of queueing networks. The first family is that of asymptotic bound analysis [Kle76,DB78]. Asymptotic bounds are obtained by considering two extreme situations: (1) no queueing takes place at any node, and (2) at least one station is saturated. These bounds do not require the product form property to hold and their computation is very fast, but they are not accurate in general. The rest of bounds that have been introduced are tighter but do require the product form assumption. This is the case of balanced job bounds [ZSEG82,Kri84], which are based on the mean value theorem [RL80]. Finally, several schemes for the construction of hierarchies of bounds have been developed that guarantee any level of accuracy (including the exact solution), by investing the necessary computational effort: performance bound hierarchies [ES83,ES86], succesively improving bounds [Sri87], generalized quick bounds [Sur84]. All these techniques are derived from mean value theorem, thus they are valid only for product form networks. 1.5 An overview of performance bounds for stochastic Petri nets Many works exist concerning the performance evaluation in the case of deterministically timed nets, mainly for strongly connected marked graphs [Ram74,Sif78,RH80,Mag84,Mur85]. We assume all these results, which can be identified as a particular case (in fact an “extreme” case) of the general stochastic timing, and we reformulate them in a general 34 CHAPTER 1. Synchronized queueing networks and Petri nets form which allows efficient computation methods. Extensions to nonordinary nets have been presented in the case of deterministic timing [Hil88]. Our work considers also these nets in a unified formulation. In the framework of stochastic Petri nets, only a few works exist related with the computation of performance bounds [Mol85,BG85,IA89], and all of them are valid just for restrictive assumptions on the nets. M. Molloy [Mol85] noted that the average token flows in an ordinary Markovian network at steady-state are conserved. Therefore, a series of flow balance equations can be written. Token flows are conserved in places so the sum of all flows into a place equals the sum of all flows out of the place. On the other hand, all token flows on the input and output arcs of a transition are equal. These equations determine the average token flows in the cycles of the net to within a constant. This constant cannot be determined without Markovian analysis at the reachability graph level. However, limit flows when the number of tokens tends to infinity can be computed. In order to do that, bottleneck transitions must be first located. Then, the actual flow through a bottleneck transition is (under saturation conditions) equal to its potential firing rate. It is well-known that the conservation of flows presented by M. Molloy is not only valid for Markovian nets. In fact, some of most important laws of queueing theory hold under very general assumptions. These general situations are considered in our work, and some fundamental laws taken from queueing theory (such as Little’s formula) are applied to stochastic Petri net models. S. Bruell and S. Ghanta [BG85] developed algorithms for computing upper and lower bounds for the throughput of a restricted subclass of generalized stochastic Petri nets (with immediate and exponentially timed transitions). The considered nets include control tokens to model a physical restriction, such as semaphores, which is not a design parameter. The rest of tokens of such nets, grouped in classes, correspond to the notion of a job or customer in a monoclass queueing network, and its number is treated as a parameter of the net. The upper and lower bounds on throughput are computed hierarchically estimating maximum and minimum time of the path followed by each class of jobs. Unfortunately, the above cited article [BG85], which is considered by the authors as a “preliminary work”, suffers from an excessive infor- 1.5. Performance bounds for stochastic PNs 35 mal style that makes confusing both the characterization of the considered net subclasses and the computation algorithms. However, in those cases in which we have been able to applied the techniques presented in [BG85], the obtained results agree with the ones that we get using the algorithms we present in this work. In the paper of S. Islam and H. Ammar [IA89], methods to compute upper and lower bounds for the steady-state token probabilities of a subclass of generalized stochastic Petri nets are presented. The considered nets are obliged to admit a time scale decomposition. This means that the transitions of the net are supposed to be divided into two classes: slow and fast transitions, with several orders of magnitude of difference in the duration of activities. Moreover, the subnets obtained after removing all slow transitions with their input and output arcs must be conservative and admit a reversible initial marking. The computation is based on near-completely decomposability of Markov chains. Our approach is different, and complementary, from the one presented in [IA89]. One objective of this text is to present algorithms for the computation of bounds for stochastic Petri nets for arbitrary mean values of service times of transitions and, moreover, for arbitrary distribution functions of the timing. This main objective is attacked in an unified framework considering both qualitative and quantitative properties of stochastic Petri nets, and laying special emphasis on structure theory of nets. The computation of both the upper and lower bounds is based on an efficient calculation of the visit ratios for transitions,a concept taken from classical queueing theory. These visit ratios, together with the average service time of transitions, the net structure, and the initial marking, are used for the derivation of proper linear programming problems whose optimum solutions are the desired bounds. In the next chapter, we focus on the computability of visit ratios from different net parameters, such as the net structure and the stochastic interpretation. Net subclasses for which this computation is possible in polynomial time are especially considered (their characterization, inclusion relations. . . ), making emphasis on those qualitative properties that are interesting from a performance point of view. 36 CHAPTER 1. Synchronized queueing networks and Petri nets 2.1. FRT-nets and subclasses 43 1. Xa=Xb, 2. ∃P⊂Psuch that XaP ∧Xb,or 3. ∃X1,...,X kT-semiflows of Nand P1,...,P k+1 ⊂P,k≥1, such that Xa P1 ∧X1 P2 ∧...Pk ∧Xk Pk+1 ∧Xb. From the above definition the next property trivially follows: Property 2.1.1 FR is an equivalence relation on the set of T-semiflows of a net. The introduction of this equivalence relation on the set of T-semiflows induces a partition into equivalence classes. FRT-nets are defined as follows: Definition 2.1.3 (FRT-nets) We say that a Petri net Nis a net with freely related T-semiflows (FRT-net, for short) iff the introduction of the freely relation on the set of its T-semiflows induces only one equivalence class. Note that FRT-nets are necessarily connected. Therefore, in what follows, unless otherwise explicitly stated, we consider only connected nets. As an example, let us consider the net depicted in figure 2.3. It is a live and structurally bounded net. Its minimal T-semiflows are: X1=(1,0,0,0,0,0,1,0,0,0,1,0,1,0)T X2=(0,1,1,0,0,0,0,1,0,0,0,0,1,0)T X3=(0,0,0,1,1,0,0,0,1,0,0,0,0,1)T X4=(0,0,0,0,0,1,0,0,0,1,0,1,0,1)T (2.5) Then, the net is an FRT-net because: X1 {p1} ∧X2 {p2} ∧X3 {p3} ∧X4(2.6) p1 p5 p3 p4 p2 t1t2t3t4 p6p7p8p9 p10 p11 p12 p13 p14 t5t6 t7t8t9t10 t11 t12 t13 t14 44 CHAPTER 2. Petri net subclasses and qualitative theory Figure 2.3: A live and structurally bounded FRT-net. 2.1.1.2 Algebraic characterization From the definition of FRT-nets, it may appears that a direct checking of the pertenence of a given net to this net subclass is not a polynomial problem on the net size. This is because the number of T-semiflows of a net can grow exponentially with the number of places and transitions. However, if structural liveness and structural boundedness are assumed, a nice characterization of the FRT-nets subclass can be obtained and checked in polynomial time. Before the presentation of that result, we introduce a second equivalence relation, now on the set of transitions of the net. Definition 2.1.4 (Equality conflict relation) [CCS90d] Two transitions taand tbare said to be in equality conflict relation, denoted by (ta,t b)∈ECR,iffPRE[ta]=PRE[tb]. Since the equality conflict relation is based on the equality of vectors, the next property follows: 2.1. FRT-nets and subclasses 45 Property 2.1.2 ECR is an equivalence relation on the set of transitions. Each equivalence class will be called equality conflict set, and denoted as ECS. Let Dbe an ECS, the number δD=|D|−1 is called number of non-redundant free conflicts of D. The reason of the name lies on the fact that δDis exactly the number of independent relations among the throughput of transitions belonging to Dthat can be derived from the routing rates defining the resolution of the conflict. The number of non-redundant free conflicts of a net, denoted as δ, is the sum of all δDcorresponding to the ECSs of the net: δ=D∈T/ECR δD. Theorem 2.1.1 Let Nbe a structurally live and structurally bounded net. Then Nis an FRT-net if and only if rank(C)=m−δ−1, where Cis the incidence matrix of N,m=|T|, and δis the number of non-redundant free conflicts of the net. Before giving the proof of the above theorem, let us state an important conclusion. Corollary 2.1.1 If Nis structurally live and structurally bounded, deciding if Nbelongs to the class of FRT-nets is polynomial on the net size. Structural boundedness of a net can be always be checked in polynomial time (iff ∃Y≥11 such that YT·C≤0 [Mur89]). Unfortunately, structural liveness of FRT-nets cannot be decided (so far) efficiently. Nevertheless, a necessary condition for a net to be structurally live structurally bounded and FRT-net can be checked in polynomial time, looking for the consistency, conservativeness, and rank condition over the incidence matrix, because structural liveness and structural boundedness implies consistency and conservativeness (see, e.g., [Sil85]). In order to prove theorem 2.1.1 we previously present some lemmatas. The first one concerns a reduction of the non-determinism at equality conflicts, preserving the liveness property, by means of the merging of a special class of nets: local schedulers. 46 CHAPTER 2. Petri net subclasses and qualitative theory Figure 2.4: Introduction of a local scheduler at an equality conflict set. Definition 2.1.5 (Local scheduler) [CCS90d] Let D={ti|i= 1,...,δ D+1}be an ECS of the net N. A local scheduler for Dis a net LSDdefined as (see figure 2.4): LSD= PLSD,T LSD,Pre LSD, PostLSD, such that TLSD∩T=D,T• LSD∪ •TLSD=PLSD, and PLSD∩P=∅. Lemma 2.1.1 Let Nbe a net and Dan ECS of N.LetLSDbe a local scheduler for D.IfNand LSDare structurally live in isolation, then the net NLSDobtained by merging the common transitions of N and LSDis structurally live. Proof. Let M0and M0LSDbe initial markings making live the nets N and LSD, respectively. Let MLSD 0be an initial marking of NLSDsuch that its projection on Pis M0and its projection on PLSDis M0LSD. Let MLSD∈R(NLSD,MLSD 0) and tbe a transition of N. We prove that there exists a firing sequence, σLSD,inN LSD,MLSDthat yields to a marking enabling t(i.e., the net NLSDis live under MLSD 0). The projection of MLSDon Pis a marking M∈R(N,M 0) from which there exists at least one σ∈L(N,M), yielding to a marking M that enables t(because the net Nis live). From this fact, three cases arise: a) If σdoes not contain any transition belonging to Dthen it is also firable in the net NLSD. b) If σcontains one transition ta∈D, that is σ=σ0taσa, then there exist δD+ 1 firable sequences from Mof the form σ0tiσi,ti∈D, (a) (b) (c) p1 p2p3 p6 p7 tatb tctd p1 tatb p2p3 p6 p7 tctd tatb p4 p5 p4 p5 2.1. FRT-nets and subclasses 47 Figure 2.5: Counter-example to the converse of lemma 2.1.1. i=1,...,δ D+1, that allow to reach a marking enabling t. This is because Nis live and M[σ0MD;∀ti∈D,MD[tiMi∈R(N,M 0) and ∀i=1,...,δ D+1, Mi[σiM i[t. Therefore, at least one of the sequences σ0tiσican be fired in NLSD:σ0and σiare firable according to the above case (a); at least one ti∈Dis firable because LSDis a live net (eventually, after the firing of some internal transitions of the local scheduler in order to enable ti). c) If σcontains more than one transition of D, we can find a firable sequence in Nthat is firable in NLSD. This can be done by applying repeatedly the above case (b). Liveness of transitions belonging to LSDcan be proved with similar arguments. Therefore, the net NLSDis live under MLSD 0and then structurally live. Unfortunately, the converse of lemma 2.1.1 is not true. Let us consider, for instance, the structurally non-live net depicted in figure 2.5.a. The net of figure 2.5.b is a structurally live local scheduler for transitions aand b. The composition of the two nets is the net of figure 2.5.c that now is structurally live. 48 CHAPTER 2. Petri net subclasses and qualitative theory In the sequel, we consider a simple class of local schedulers called regulation circuits. These nets are used as a tool to prove the theorem 2.1.1. Nevertheless, they are not the unique local schedulers that can be used for that purpose. Definition 2.1.6 (Regulation circuit) [CCS90d] Let taand tbbe two transitions of Nin equality conflict relation. A regulation circuit for taand tbis a net rab =Prab ,T rab ,Pre rab , Postrab , where Prab = {pab,p ba},Trab ={ta,t b},•pab ={ta},p• ab ={tb},PRErab [pab,t b]= POSTrab [pab,t a]=1,•pba ={tb},p• ba ={ta}, and PRErab [pba,t a]= POSTrab [pba,t b]=1. As an example, the local scheduler depicted in figure 2.5 is a regulation circuit for taand tb. The composition of Nand rab (by merging the common transitions taand tb) will be denoted as Nrab . The incidence matrix of Nrab will be denoted as Crab . Let Nbe a net and D={ti|i=1,...,δ D+1}be an ECS. The net obtained from Nby adding a regulation circuit per each pair of transitions tk,t k+1 ∈D,k =1,...,δ D, will be denoted as NRD, and its corresponding incidence matrix as CRD. The net obtained by adding regulation circuits for all ECSs as above will be denoted as NR, and its corresponding incidence matrix as CR. The following lemmatas present some properties of NRDderived from the corresponding properties of N. Lemma 2.1.2 Let Nbe a net and D={ti|i=1,...,δ D+1}be an ECS. If Nis structurally live and structurally bounded then NRDis structurally live and structurally bounded. Proof. The set of regulation circuits added to Nis a local scheduler for D. This local scheduler is structurally live in isolation (this is obvious, putting enough tokens at each of the regulation circuits). The net Nis also structurally live and then, by lemma 2.1.1, the net NRDis structurally live. All places of Nare structurally bounded. Taking into account the definitions of ptktk+1 and ptk+1tkit is easy to see that CRD[ptktk+1 ]+ CRD[ptk+1tk] = 0 (i.e., the sum of the rows in the incidence matrix corresponding to these places is zero). Therefore all new places added to 2.1. FRT-nets and subclasses 49 Nare also structurally bounded and then NRDis structurally bounded. Lemma 2.1.3 Let D={ti|i=1,...,δ D+1}be an ECS. If Nis structurally live and structurally bounded then min{m−1,n+2δD−1}≥rank(CRD)=rank(C)+δD(2.7) Proof. NRDis structurally live and structurally bounded (lemma 2.1.3), thus conservative and consistent [Sil85]. Therefore, rank(CRD)≤min{mRD−1,n RD−1}, where mRD=|TRD|=|T|=m and nRD=|PRD|=|P|+|Pr12 |+···+|Prkk+1 |+···+|PrδD−1δD|=n+2δD. So, we obtain: rank(CRD)≤min{m−1,n+2δD−1}. Let Npt2t1be a net obtained from Nby adding the place pt2t1belonging to the regulation circuit r1,2.Npt2t1is non-conservative because for all marking that enables the transitions of Dwe can decide to fire always the transition t2(i.e., the place pt2t1is structurally unbounded). Then we can conclude that there is not a vector Y such that YT·C=Cpt2t1[pt2t1] (see proposition 2.8 in [CCS90d]) (i.e., the row vector Cpt2t1[pt2t1] is linearly independent with respect to the row vectors of the incidence matrix of the net N). Therefore, rank(Cpt2t1)=rank(C) + 1. If we add the place pt1t2to the net Npt2t1we obtain the net Nr1,2. This last net has the same rank that the net Npt2t1because Cr1,2[pt2t1]=−Cr1,2[pt1t2]. Therefore, rank(Cr1,2)=rank(C)+1. Let NRk−1be the net obtained from Nby adding the regulation circuits r1,2,...,r k−1,k.NRk−1verifies rank(CRk−1)=rank(C)+k−1. We prove now that if we add the regulation circuit rk,k+1 to the net NRk−1then rank(CRk)=rank(CRk−1)+1. We add the place ptk+1tkbelonging to the regulation circuit rk,k+1 to the net NRk−1. This place is unbounded because for all marking that enables some transition of the set {t1,...,t k},tk+1 is also enabled at this marking and then we can decide to fire always the transition tk+1. Then the row vector CRk[ptk+1tk] is linearly independent with respect to the row vectors of the incidence matrix of the net NRk−1(by proposition 2.8 in [CCS90d]). Therefore, rank(CRk)=rank(CRk−1)+1 (because CRk[ptk+1tk]=−CRk[ptktk+1 ]). 50 CHAPTER 2. Petri net subclasses and qualitative theory The number of added regulation circuits is δD, hence rank(CRD)= rank(C)+δD. Lemma 2.1.4 Let Nbe a structurally live and structurally bounded net. Then rank(C)≤m−δ−1, where Cis the incidence matrix of N,m=|T|, and δis the number of non-redundant free conflicts of the net. Proof. Nis conservative and consistent [Sil85]. If we add a local scheduler per each ECS of the net, we obtain a net denoted NRthat satisfies: min{m−1,n+2δ−1}≥rank(CR)=rank(C)+δ. Then, rank(C)≤min{m−δ−1,n+δ−1}. Taking into account that the net Nis conservative and consistent, we also have that rank(C)≤ min{m−1,n−1}. Therefore, combining the two above upper bounds of rank(C), we obtain: rank(C)≤min{m−δ−1,n−1}. But, N being conservative, rank(C)≤n−1 and the lemma follows. Proof of theorem 2.1.1. The rank equality condition holds iff NR has a unique minimal T-semiflow. So let us prove this condition. The number of minimal T-semiflows of NRis greater than or equal to 1 because this net is consistent. We compute T-semiflows, X≥0 and C·X= 0, applying the algorithm presented in [CS89b] to the net NR. To do so, we eliminate first the places ptiti+1 that connect two transitions in equality conflict relation (obviously, if we eliminate ptiti+1 we also eliminate pti+1tibecause CR[ptiti+1 ]=−CR[pti+1ti]). The elimination of ptiti+1 generates a unique new column that is a linear combination of the columns corresponding to tiand ti+1. In order to eliminate pti+1ti+2 we generate again a unique column that is a linear combination of the above added column and the column of ti+2. If we repeat this procedure for all places ptiti+1 belonging to an ECS we obtain a unique new column in which all entries corresponding to places of the local scheduler are zero. The non-null entries of this row are •ECS ∪ECS•. Applying this procedure for all ECS of the net we obtain a matrix in which there is a new column per ECS and all columns in the original net corresponding to transitions that do not belong to any ECS. This matrix can be interpreted as the incidence matrix of a new net with at most one minimal T-semiflow iff the original net is an FRT-net. This is because, if the original net was 2.1. FRT-nets and subclasses 51 an FRT-net, all its T-semiflows would be freely related (by definition of FRT-net), thus freely connected by pairs. And this occurs iff after the application of the above procedure (i.e., after the addition of the regulation circuits) each pair of originally freely connected T-semiflows constitute a unique T-semiflow. Therefore, applying the rank formula of lemma 2.1.3 with rank(CR)=m−1 we obtain: rank(C)=m−δ−1. 2.1.1.3 Qualitative properties The next result gives a method for the computation of the vector of visit ratios for transitions of a structurally live and structurally bounded FRT-net (provided liveness), from the knowledge of the net structure and the routing rates at equality conflict sets. Theorem 2.1.2 Let Nbe a structurally live and structurally bounded FRT-net. Let Cbe the incidence matrix of N, and Rthe matrix (with δ independent rows, where δis the number of non-redundant free conflicts of N) that defines the relative rates of transitions in equality conflict relation (i.e., the routing at the equality conflict sets). Then, the vector of visit ratios v(j)normalized, for instance, for transition tjcan be computed from Cand Rsolving the following linear system of equations: C R·v(j)=0,v (j) j=1 (2.8) (Note that this computation only makes sense when infinite behaviour is possible for the net from a given initial marking, in other words, when the net is deadlock-free.) Proof. We only have to check that the above system has a unique solution. By theorem 2.1.1, the number of independent rows of matrix Cis m−δ−1. Therefore, the m−δ−1 independent conditions given by C·v(j)= 0 plus the δindependent conditions given by R·v(j)=0 plus the normalization condition v(j)(tj) = 1 are enough to determine exactly the mcomponents of the vector v(j). 52 CHAPTER 2. Petri net subclasses and qualitative theory From the above theorem, as we announced previously, for structurally live and structurally bounded FRT-nets we have: v(j)=ϕ(N,R)(2.9) and the next complexity result follows: Corollary 2.1.2 The computation of the vector of visit ratios for transitions of a structurally live and structurally bounded FRT-net is polynomial on the net size. As an example, let us consider again the net depicted in figure 2.3. The vector of visit ratios must be a right annuller of the incidence matrix, hence a linear combination of a basis of T-semiflows: v(1) = 4  i=1 αiXi(2.10) where Xi,i=1,...,4, are the minimal T-semiflows (2.5) of the net. If r1,r2are the routing rates of t1,t2in the conflict at p1;r3,r4the routing rates of t3,t4in the conflict at p2; and r5,r6the routing rates of t5,t6in the conflict at p3, then v(1) must satisfy: r2v(1) 1=r1v(1) 2 r4v(1) 3=r3v(1) 4 r6v(1) 5=r5v(1) 6 (2.11) And together with the normalization requirement: v(1) 1=1 (2.12) the four parameters αi,i=1,...,4, can be determined. Another interesting qualitative property follows from theorem 2.1.2, that does not hold for general nets: Property 2.1.3 Let Nbe a structurally live and structurally bounded FRT-net. Then Nis live if and only if it is deadlock-free. 2.1. FRT-nets and subclasses 59 X2=X+kX, taking k>0 large enough, and this is against the hypothesis of mono-T-semiflow. From previous theorem, the next statement follows: Corollary 2.1.3 If Nis consistent, deciding if Nbelongs to the class of mono-T-semiflow nets is polynomial on the net size. Now, we present an efficient method for the computation of the vector of visit ratios for transitions of a structurally live and structurally bounded mono-T-semiflow net (provided liveness), from the net structure. It follows from theorems 2.1.2 and 2.1.4. Theorem 2.1.5 Let Nbe a structurally live and structurally bounded mono-T-semiflow net and Cits incidence matrix. Then, the vector of visit ratios v(j)normalized, for instance, for transition tjcan be computed from Csolving the following linear system of equations: C·v(j)=0,v (j) j=1 (2.13) From the above theorem, for structurally live and structurally bounded mono-T-semiflow nets we have: v(j)=ϕ(N)(2.14) and the next complexity result follows: Corollary 2.1.4 The computation of the vector of visit ratios for transitions of a structurally live and structurally bounded mono-T-semiflow net is polynomial on the net size. Since mono-T-semiflow nets are FRT-nets, the “good” properties exhibited for these are inherited by those. Related with the “bad” results presented for general FRT-nets in properties 2.1.4, 2.1.5, 2.1.6, 2.1.7, and 2.1.8, the same can be stated for mono-T-semiflow nets. This can be seen looking at the FRT-nets depicted in figures 2.6, 2.7, 2.8, and 2.9, that were used as counter-examples. All of them are also mono-T-semiflow nets. In the next section, we identify a subclass of mono-T-semiflow nets for which some of the previous negative results change. 60 CHAPTER 2. Petri net subclasses and qualitative theory 2.1.2.2 Structurally decision-free nets Let us introduce a class of structurally defined nets for which never exist conflicts, whichever it is the initial marking. Definition 2.1.9 (Structurally decision-free nets) [CCS89] A net Nis said to be structurally decision-free iff for all place p:|p•|≤1. For example, the net depicted in figure 2.8 is a live structurally bounded and structurally decision-free net. Now, we prove that all structurally live structurally bounded and structurally decision-free nets are mono-T-semiflow: Property 2.1.10 Let Nbe a connected, consistent, and structurally decision-free net. Then Nis mono-T-semiflow. Proof. Since the net is consistent, it has at least a T-semiflow. It has not more than one because if a transition belongs to a T-semiflow X, all output transitions of its output places must belong to X(because the net is structurally decision-free). Since the net is connected there exists at most one T-semiflow. The reverse of property 2.1.10 is not true. For example the net of figure 2.10 is mono-T-semiflow but is not structurally decision-free. Thus, consistent and structurally decision-free nets constitute a proper subclass of mono-T-semiflow nets. We have seen that, in general, live structurally bounded mono-Tsemiflow nets have not home state. However the subclass of deadlockfree and bounded structurally decision-free nets have home state. Property 2.1.11 Let N,M 0be a deadlock-free and bounded structurally decision-free net. Then, it has a home state. Proof. Boundedness of the net guarantees a bounded number of reachable markings. In this case, the absence of decisions assures the existence of home state. As a corollary, ergodicity of the marking process of such nets follows: Corollary 2.1.5 Let N,M 0be a bounded structurally decision-free net. Then its marking process is weakly ergodic. Moreover, if the net is Markovian, its marking process is strongly ergodic. 2.1. FRT-nets and subclasses 61 2.1.2.3 Marked graphs In this section, ordinary structurally decision-free nets without multiple attributions to places are considered: the well-known subclass of em marked graphs. Marked graphs can be seen as a generalization of the classical PERT tool [MP70]. With PERT model, the relationship among the tasks of a project can be represented by a network of activities (arrows) and events (nodes). Timing interpretation can be added to activities for the purpose of evaluating the completion time of the project. The obtained network is an acyclic graph, i.e., repetitive systems cannot be modelled. With marked graphs, cyclic behaviours can be modelled as well as many different classes of non shared resources for the realization of activities (tokens at places of the net). Let us briefly recall what marked graphs are and some of their basic properties. Marked graphs allow to model concurrency and synchronization but no decisions because they are structurally decision-free nets. Definition 2.1.10 (Marked graphs) [CHEP71] Marked graphs are ordinary Petri nets (i.e., preand post-incidence functions taking values in {0,1}) such that for all place p:|•p|=|p•|=1. Property 2.1.12 Let Nbe a marked graph. 1. Nis structurally decision-free. 2. Nis consistent and its unique minimal T-semiflow is X=11. 3. The vector of visit ratios for transitions of Nis v =11(provided liveness), independently of the initial marking and of the average service times associated with transitions. The reverse of property 2.1.12.1 is not true. For example, the net depicted in figure 2.8 is structurally decision-free but it is not a marked graph. Some interesting results from qualitative theory of marked graphs are recalled bellow. In particular, checking their liveness characterization is polynomial on the net size. 62 CHAPTER 2. Petri net subclasses and qualitative theory Theorem 2.1.6 [Mur89] Let N,M 0be a marked graph. 1. The elementary P-semiflows of Nare exactly its directed circuits. 2. N,M 0is live iff all its directed circuits are marked. Putting an initial marking large enough, after marking all circuits the system will be live: Corollary 2.1.6 Marked graphs are structurally live. Corollary 2.1.7 The liveness of a marked graph can be decided in polynomial time on its size, checking that there is no unmarked P-semiflow:  ∃Y≥ \0,Y T·C=0,Y T·M0=0 (2.15) From the theorem 2.1.6.2, the following liveness monotonicity result follows: Corollary 2.1.8 If N,M 0is a live marked graph and M 0≥M0then N,M 0is live. For live marked graphs, boundedness and structural boundedness are equivalent properties: Property 2.1.13 [Sil85] Let Nbe a marked graph. 1. The following three statements are equivalent: i) Nis structurally bounded. ii) Nis strongly connected. iii) Nis conservative (i.e., ∃Y≥11,YT·C=0). 2. Let N,M 0be live. Then N,M 0is bounded iff Nis structurally bounded. Hopefully, the reachability problem, i.e., the efficient characterization of reachable markings, has a satisfactory solution for live marked graphs: 2.1. FRT-nets and subclasses 63 Theorem 2.1.7 [Mur77] Let N,M 0be a live marked graph. The three following statements are equivalent: i) M∈R(N,M 0), i.e., Mis reachable from M0. ii) M=M0+C·σ, with M,σ≥0. iii) Bf·M=Bf·M0, with Bfthe fundamental circuit matrix of the graph, and M≥0. According to the above theorem M∈R(N,M 0) if and only if M0∈ R(N,M). In other words: Corollary 2.1.9 Live marked graphs are reversible. Weak ergodicity of the firing and the marking processes for live and strongly connected marked graphs follows (from corollary 2.1.5), since they are bounded and structurally decision-free nets: Corollary 2.1.10 The firing process of a live marked graph is weakly ergodic. If the net is strongly connected the marking process is also weakly ergodic. Moreover, if the net is Markovian, its marking process is strongly ergodic. Finally, the next interesting property of live marked graphs, can be deduced: Property 2.1.14 Let N,M 0be a marked graph, and ta transition of N. Then E(t)=L(t)=SE(t). Proof. Marked graphs are reversible, by corollary 2.1.9. Then, by property 1.2.2, E(t)=L(t) for all transitions t. Finally, E(t)=SE(t), by theorem 2.1.7.i and ii. This allows an efficient computation of enabling and liveness bounds based on the linear programming problem (LPP1) that characterizes the structural enabling bound of transitions. 64 CHAPTER 2. Petri net subclasses and qualitative theory 2.1.3 Free choice nets Another interesting subclass of FRT-nets is that of free choice nets. Free choice nets [Hac72] are a well-known subclass of ordinary Petri nets that hold a particularly restricted interplay between concurrency and decisions. They are rich enough to be non-trivial but restricted enough to allow a number of interesting results that do not hold in general and that constitute a quite elegant theory (see, e.g., [Hac72, TV84,Bes87,CCS90a,Esp90,ES90]). Free choice nets allow both synchronization and conflict but in a restricted and disciplinated way. In a free choice net, if a place has a shared output transition then it is the only output transition of this place. And, equivalently, if a transition has a shared input place then it is the only input place of this transition. Definition 2.1.11 (Free choice nets) [Hac72] Free choice nets are ordinary Petri nets (i.e., preand post-incidence functions taking values in {0,1}) such that for all place p:|p•|>1⇒•(p•)={p}. Since all decisions are free in a free choice net, all the T-semiflows are freely related and the following inclusion holds: Property 2.1.15 Free choice (connected) nets are FRT-nets. Let us remark also that marked graphs, presented in previous section, are free choice nets. This section introduces a minimum of qualitative results from the large body of free choice nets theory. Additional qualitative results are derived from the quantitative/performance based approach introduced in this work. This approach clearly points out the interest of interleaving the qualitative and quantitative theories. Let N=P, T, Pre, Postbe a Petri net and P⊆P.N= P,T,Pre , Postis called a P-component of Niff Nis the subnet of Ngenerated by P(i.e., T⊆Tand Pre, Postare the restrictions of Pre, Post to Pand T) and ∀t∈T:|•t∩P|≤1∧|t•∩P|≤1. An important result in the structure theory of free choice nets assures that each minimal P-semiflow of a structurally live and structurally bounded free choice net generates a P-component, and that liveness can be assured when all the P-components are marked: 2.1. FRT-nets and subclasses 65 Theorem 2.1.8 Let N=P, T, Pre, Postbe a structurally live and structurally bounded free choice net. 1. [ES90] Y≥0is a minimal P-semiflow of Niff the two following conditions hold: a) ∀p∈P:Y(p)∈{0,1} b) ∃N =P,T,Pre , PostP-component of Nand ||Y|| = P 2. [Esp90] If M0is a given initial marking for N,N,M 0is live if and only if all its P-components are marked. Note that the above theorem is a generalization of theorem 2.1.6 (stated for marked graphs), for the case of structurally live and structurally bounded free choice nets. The characterization of liveness for such nets is the same than for marked graphs (corollary 2.1.7): Corollary 2.1.11 The liveness of a structurally live and structurally bounded free choice net can be decided in polynomial time on its size, checking that there is no unmarked P-component:  ∃Y≥ \0,Y T·C=0,Y T·M0=0 (2.16) From the previous characterization of liveness, a monotonicity result trivially follows for structurally bounded nets: Corollary 2.1.12 If N,M 0is a live structurally bounded free choice net and M 0≥M0then N,M 0is live. In fact, structural boundedness is not necessary in the previous property (since liveness monotonicity can be derived from a more general characterization of liveness for free choice nets [Hac72]). Unfortunately, for general (non-structurally bounded) free choice nets, the following “bad” result has been proven: Theorem 2.1.9 [JLL77] Let N,M 0be a free choice net. The decision of non-liveness for N,M 0is NP-complete. 66 CHAPTER 2. Petri net subclasses and qualitative theory As in the more general case of live and bounded FRT-nets, weak ergodicity of the firing process is assured (and strong ergodicity for Markovian nets), and the vector of visit ratios can be computed in polynomial time from the net structure and the routing rates at conflicts, solving the system 2.8 presented in section 2.1.1. A particular version of the rank theorem of structurally live and structurally bounded FRT-nets (cfr. theorem 2.1.1) for free choice nets can be stated: Theorem 2.1.10 [CCS90a] Let Nbe a strongly connected structurally bounded free choice net. Then the net is structurally live iff rank(C)= m−1−(a−n), where Cis the incidence matrix of N,m=|T|,n=|P|, and ais the number of input arcs to transitions. The importance of this statement for free choice nets lies on the fact that several key results of free choice theory appear as corollaries. For example, the characterization of simultaneous structural liveness and structural boundedness in free choice nets is of polynomial complexity, therefore, from theorem 2.1.8.2, the next result follows: Corollary 2.1.13 Let N,M 0be a structurally bounded free choice net. Then it can be decided in polynomial time on the number of arcs of Nif the marked net is live, checking the rank characterization for structural liveness (theorem 2.1.10) and if all P-components are marked (with the algebraic characterization of corollary 2.1.11). The following duality result follows also from theorem 2.1.10: Corollary 2.1.14 Let N=P, T, Pre, Postbe a free choice net. N is structurally live and structurally bounded iff the reverse-dual of N, Nrd =T, P, Post, Pre, is structurally live and structurally bounded. Proof. If Nis connected structurally live and structurally bounded then it is strongly connected, consistent, and conservative [CCS90d]. Then Nrd is strongly connected, consistent, and conservative, thus structurally bounded. Finally, since rank(C)=rank(Crd), mrd =n,nrd =m, and ard = a,wehavemrd −1−(ard −nrd)=n−1−(a−m)=m−1−(a−n), i.e., if Nis structurally live then Nrd is also structurally live. 2.1. FRT-nets and subclasses 67 Based on [BV84], W. Vogler proved in 1989 that a live and bounded free choice net has at least one home state. Theorem 2.1.11 [Vog89] Let N,M 0be a live and bounded free choice net. Then N,M 0has a home state. The importance of the previous result from the performance evaluation point of view is stated in the next corollary (see section 1.2.3.3): Corollary 2.1.15 Let N,M 0be a stochastic live and bounded free choice net. Then its marking process is weakly ergodic. Moreover, if the net is Markovian, its marking process is strongly ergodic. As in the case of marked graphs, for live and bounded free choice nets, it is possible to show that SB(p)=B(p). Theorem 2.1.12 [Esp90] Let N,M 0be a live and bounded free choice net, then for all place pof N:B(p)=SB(p). In other words, the structural marking bound is always reached in a live and bounded free choice net, and the next result follows: Corollary 2.1.16 A live free choice net is bounded iff it is structurally bounded. The importance of the above results lies on the fact that marking bounds can be efficiently computed (looking for the structural ones) and, in particular, that boundedness can be algebraically characterized (∃Y≥11 such that YT·C≤0 [Mur89]). Using theorem 2.1.12, an interesting property of live and bounded free choice nets, that allows an efficient computation of liveness bound of transitions, can be derived: Theorem 2.1.13 Let N,M 0be a live and bounded free choice net. Then, for all transition tof N:E(t)=L(t)=SE(t). 68 CHAPTER 2. Petri net subclasses and qualitative theory Proof. Let tibe a given transition of N. A new live and bounded free choice net N ,M 0is obtained by splitting transition tiinto a transition ti1, an unmarked place pi, and another transition ti2. Then, for tiand pi:SE(ti)=SB(pi) and E(ti)=B(pi). Since for live and bounded free choice nets B(pi)=SB(pi) (cfr. theorem 2.1.12) then E(ti)=SE(ti). Live and bounded free choice nets are structurally bounded (corollary 2.1.16) and live. Since structurally bounded nets are conservative [Sil85], the structural marking bound coincides with the bound obtained from a basis of P-semiflows: SB(pi) = max{M(pi)|BT·M= BT·M 0,M ≥0}[CS89c]. Let Mhbe a home state of N ,M 0(its existence is guaranteed by theorem 2.1.11). Because Mhis reachable from M 0,BT·Mh=BT·M 0. Considering as a new starting time that in which Mhis reached for the first time: SB(pi) = max{M(pi)|BT·M=BT·Mh,M ≥0}.Thus SB(pi) is reached from a home state, and E(ti)=L(ti). Now, from the previous theorem and taking into account that for any transition tthe computation of the structural enabling bound SE(t) can be formulated in terms of the problem (LPP1), the following monotonicity property of the liveness bound of a transition with respect to the initial marking is obtained: Corollary 2.1.17 If N,M 0is a live and bounded free choice net and M 0≥M0then the liveness bound of tin N,M 0is greater than or equal to the liveness bound of tin N,M 0. The previous result appears to be a generalization (stated for the particular case of bounded nets) of the classical liveness monotonicity property for free choice nets stated in corollary 2.1.12. Finally, let us define state machines, a well-known subclass of free choice nets: Definition 2.1.12 (State machines) State machines are ordinary Petri nets (i.e., preand post-incidence functions taking values in {0,1}) such that for all transition t:|•t|=|t•|=1. p1 1 p1 2 1 t1 1 t2 b1 b2 b3 3 t1 3 t2 3 p1 3 p2 2 t3 2 t2 2 t1 2 p1 2 p2 2.1. FRT-nets and subclasses 75 Figure 2.13: A totally open deterministic system of sequential processes. ergodic such systems are derived. Moreover, in chapter 5 we prove that the ergodicity characterization and the exact computation of steadystate performance measures is possible in polynomial time on the net size for these nets (assuming exponential timing). Definition 2.1.16 (Totally open deterministic systems of sequential processes) [CS89a] A deterministic system of sequential processes is called totally open iff the underlying net has not any circuit containing buffers. An example of totally open deterministic system of sequential processes is depicted in figure 2.13. Some interesting qualitative results can be derived from the structure of these nets. Liveness of totally open deterministic systems of sequential processes and unboundedness of the buffers are presented in theorem 2.1.16. In theorem 2.1.17, consistency (necessary condition for marking ergodicity of live Markovian nets, cfr. theorem 1.2.3) is shown to collapse with existence of home state for this subclass of nets. Theorem 2.1.16 Let N,M 0be a totally open deterministic system of sequential processes. Then N,M 0is live and all buffers are unbounded. 76 CHAPTER 2. Petri net subclasses and qualitative theory Proof. Let be N ,M 0=P1∪...∪Ps∪B,T1∪...∪Ts, Pre, Post, M0. All Ni,M 0|i=Pi,T i,Pre|i, Post|i,M 0|iare live in isolation (by property 2.1.16, because M0marks all the state machines by definition 2.1.14.ii). All transitions of those state machines without input buffers can be fired an infinite number of times, independently of the rest, so all the output buffers of these machines do not restrict the firing of the other machines. This argument can be repeated for all the system because of the absence of circuits containing buffers. Thus, the net is live. From the liveness of the system and from the fact that buffers are not contained in any circuit, the input transitions of buffers can be fired an infinite number of times without firing their output transitions. Thus, all buffers are unbounded. An interesting property of live marked graphs, presented in theorem 2.1.7, that states a bridge between its behavioural and structural analysis is that all potentially reachable markings are reachable. It is also true for totally open deterministic systems of sequential processes: Property 2.1.19 Let N,M 0be a totally open deterministic system of sequential processes. Then M∈R(N,M 0)iff M∈PR(N,M 0).In other words, each vector σ ∈IN msuch that M0+C·σ ≥0corresponds at least to one firable sequence in Nfrom M0. Proof. Let σ ∈IN mbe such that M0+C·σ ≥0. All transitions represented in σ belonging to state machines without input buffers (Ni1,...,Nir) are firable at first. Then, transitions belonging to state machines whose input buffers are output of Ni1,...,Nircan be fired. This procedure can be repeated for all state machines since no circuits containing buffers exist. The following theorem relates, for totally open deterministic systems of sequential processes, a behavioural property (existence of home state) with a structural one (consistency). Theorem 2.1.17 Let N,M 0be a totally open deterministic system of sequential processes. Then Nis consistent iff M0is a home state. t 1 t1 b1 b2 2 t2 2 t1 2 p12 p2 p1 1p1 2 1 2 1 t3 2.1. FRT-nets and subclasses 77 Figure 2.14: A non-consistent totally open deterministic system of sequential processes. Proof. Let us suppose that there exists X∈(IN+)msuch that C·X= 0 (i.e., the net is consistent). Let M∈R(N,M 0) and σsuch that M0[σM. Let k∈IN be such that kX ≥σ. Then,  δ=kX −σ ≥0, M0[σM[δM0(fireability of δis deduced from property 2.1.19) and M0 is a home state. Let us suppose that M0is a home state. Since the net is live (cfr. theorem 2.1.16), there exist a marking M1and a firing sequence σ1including all transitions such that M0[σ1M1. Since M0is a home state, there exists a firing sequence σ2such that M1[σ2M0. Then the vector σ1+σ2∈(IN+)mis such that C·(σ1+σ2) = 0, where Cis the incidence matrix of the net. Therefore, Nis consistent. In theorem 1.2.3, a necessary condition for the marking ergodicity of a live Markovian Petri net is shown. Now, let us remark that there exist non-consistent totally open deterministic systems of sequential processes (see figure 2.14: M(b1)−M(b2)=σ(t1 1)−σ(t3 1)=σ(t1 1)− [σ(t1 1)−σ(t2 1)−M(p1 1)] = M(p1 1)+σ(t2 1). Since the net is live, σ(t2 1)→ ∞⇒M(b1)−M(b2)→∞⇒structurally marking non-ergodic net). Then, in practice, it is convenient to check consistency (a polynomial time computation) of the underlying net before computing marking ergodicity conditions for a given Markovian interpretation of the totally open deterministic system of sequential processes. Taking into account the above remark and theorem 1.2.3, the following result with practical interest can be stated: b1b2 p1 1 p1 2 1 t1 1 t2 1 t3 2 2 t2 2 t1 2 p1 p2 2 t2 2 t1 2 p1 2 p2 1 b 2 b 1 t2 1 t1 1 p1 1 p2 (a) Structurally non-ergodic: (•b ,•b )∉SDR; (b •,b • )∈SDR. 11 22 (b) Potentially ergodic: (•b ,•b )∈SDR; (b •, b • )∈SDR. 1122 78 CHAPTER 2. Petri net subclasses and qualitative theory Figure 2.15: Consistent totally open deterministic systems of sequential processes with two state machines and two buffers. Corollary 2.1.18 There exist totally open deterministic systems of sequential processes that are marking non-ergodic for all timing interpretation. In particular, non-consistent systems are always marking nonergodic. Unfortunately, it cannot be stated that if N,M 0is a consistent totally open deterministic system of sequential processes, there exists a Markovian interpretation such that the stochastic net is marking ergodic. The net in figure 2.15.a is consistent but there does not exist any Markovian interpretation making it marking ergodic: the case of (exponential) distribution rates λ2 1=λ3 1(of course, only possible in theory!) leads to a null recurrent Markov process and so non-ergodic, because the marking process at buffers b1and b2can be shown to be isomorphic to a symmetrical random walk [Rev84]. The rest of this section is devoted to the study of necessary and sufficient conditions for the “potential marking ergodicity” of systems. We say that a net is potentially marking ergodic iff there exists a Markovian interpretation (i.e., an assignment of exponential random timing) 2.1. FRT-nets and subclasses 79 that can lead to marking ergodic systems. For characterizing the possible existence of a Markovian interpretation making marking ergodic a given totally open deterministic system of sequential processes, let us give local rules that will be composed step by step for a large system. As a first step, a necessary and sufficient condition for a deterministic system of two sequential processes to be potentially marking ergodic in terms of consistency of the net and of some synchronic distance relations among transitions is presented. After that, a “transitivity rule” for systems composed by three state machines is presented. It gives a necessary and sufficient condition for such systems to be potentially marking ergodic. An iterative application of the presented rules leads to the derivation of necessary and sufficient conditions for a general totally open deterministic system of sequential processes to be potentially marking ergodic. Let us now recall the concept of global synchronic distance relation. If two subsets of transitions are in global synchronic distance relation then it is not possible to fire an infinite number of times some transition of the first subset without firing any transition of the second subset, and vice versa. Even more, if two subsets of transitions are in global synchronic distance relation they behave like if they were included in a regulation circuit (see definition 2.1.6). Global synchronic distance relation is used below for finding necessary and sufficient conditions for the existence of a Markovian interpretation that makes marking ergodic a totally open deterministic system of sequential processes. Definition 2.1.17 (Global synchronic distance relation) [Sil87] Let N,M 0be a Petri net and T1,T 2subsets of transitions. T1and T2 are in global synchronic distance relation, denoted as (T1,T 2)∈SDR, iff ∃W1,W 2∈IN mvectors which express the weights associated with the transitions of the subsets T1and T2(i.e., ||W1|| =T1and ||W2|| =T2), and ∃k∈IN such that sup σ∈L(N,M) M∈R(N,M0) |(W1−W2)T·σ|≤k(2.22) 2 t2 1 b 2 b 3 p3 3 t13 t2 3 t33 t4 3 p1 3 p2 1 t3 1 t2 1 t1 1 p11 p2 2 t12 p1 2 p2 80 CHAPTER 2. Petri net subclasses and qualitative theory Figure 2.16: Structurally marking non-ergodic system with three state machines. The first result is a negative one. If a given state machine receives tokens from two different state machines, one of them without input buffers, the system cannot be marking ergodic (see figure 2.16). Theorem 2.1.18 Let N,M 0=P1∪... ∪Ps∪B,T1∪... ∪ Ts, Pre, Post, M0be a totally open deterministic system of sequential processes such that for one of their communicating state machines Ni,M 0|i=Pi,T i,Pre|i, Post|i,M 0|i: a) ∃b1such that b• 1⊆Ti(i.e., it is an input buffer of the machine Ni,M 0|i) and •b1⊆Tj, where Tjis the set of transitions of another state machine Nj,M 0|jsuch that  ∃b∈Bsatisfying b•⊆Tj(i.e., the input state machine of buffer b1has not input buffers), and b) ∃b2such that b• 2⊆Ti(i.e., another input buffer of the machine Ni,M 0|i) and •b2⊆ Tj(i.e., the input state machine of buffer b2is not Nj,M 0|j). Then, there is no Markovian interpretation such that the corresponding stochastic net is marking ergodic. Proof. The arrival processes of tokens to buffers b1and b2are Poissonlike independent stochastic processes [Ros83] joint by a state machine. 2.1. FRT-nets and subclasses 81 Then, the underlying Markov chain is transient (in the case in which the marking of one buffer tends to infinity with time) or null recurrent (case os stochastic equilibrium, equivalent to a symmetrical random walk) but never positive recurrent. Now, let us give necessary and sufficient conditions for the existence of a Markovian timing interpretation that makes marking ergodic a system composed by two state machines (see figures 2.14 and 2.15). Basically, the net must be consistent and for each pair of buffers between both state machines, the input (output) transitions of one buffer cannot fire an infinite number of times without firing the input (output) transitions of the other buffer. In this way, null recurrency of the associated Markov process is discarded. Theorem 2.1.19 Let N,M 0=P1∪P2∪B,T1∪T2, Pre, Post, M0 be a totally open deterministic system of sequential processes composed by two state machines and a set of buffers Bsuch that ∀b∈B:•b⊆ T1,b •⊆T2. Then, there exists a Markovian interpretation making marking ergodic the system if and only if: i) Nis consistent and ii) ∀bi,b j∈B:(•bi,•bj)∈SDR and (b• i,b • j)∈SDR. Proof. Let us suppose that there exists a Markovian timing making marking ergodic the system. Then the net is consistent by theorem 1.2.3. If (•b1,•b2)∈ SDR or (b• 1,b • 2)∈ SDR then the marking of b1and b2cannot be linearly expressed the one in function of the other. These buffers have two non-equal arrival rates, joint by a unique server (the state machine). Thus, the underlying Markov chain is transient or null recurrent, but never positive recurrent. Therefore, it is marking non-ergodic. Now, let us suppose that (i) and (ii) hold. Let us consider b1,b 2∈B. Let us denote •b1=T11,•b2=T12,b• 1=T21, and b• 2=T22. Since (T11,T 12)∈SDR and (T21,T 22)∈SDR, there exist vectors W11,W 12,W 21,W 22 ∈IN mwith ||Wij|| =Tij,i,j =1,2 (see definition 2.1.17) such that two regulation circuits can be added without changing the behaviour of the net, as follows (see figure 2.17): s11 s12 s21 s22 b1b2 1 r 2 r 2 r 1 r b •1 b• 1 b •2 b• 2 1 2 M M 82 CHAPTER 2. Petri net subclasses and qualitative theory Figure 2.17: Regulation circuits between transitions in global synchronic distance relation. P 1=P1∪{s11,s 12}with s• 11 =•s12 =T11,•s11 =s• 12 =T12, and Pre(s11,t)=Post(s12,t)=W11(t),∀t∈T11,Pre(s12,t)= Post(s11,t)=W12(t),∀t∈T12. P 2=P2∪{s21,s 22}with s• 21 =•s22 =T21,•s21 =s• 22 =T22, and Pre(s21,t)=Post(s22,t)=W21(t),∀t∈T21,Pre(s22,t)= Post(s21,t)=W22(t),∀t∈T22. Now, from consistency of the net: ∃X≥11 such that C·X=0. Then, the column vectors of the incidence matrix (of the modified net) corresponding with transitions T11,T 12,T 21, and T22 must be linearly independent, or equivalently: W11 =W21 and W12 =W22. This implies that the markings of both buffers are linearly independent. The argument above can be applied to all pair of buffers of the net. Then, the marking of all of them can be expressed in terms of the marking of one buffer and the marking of the state machines. Then, a Markov timing can be associated such that the interarrival times of tokens to the buffers are greater than the “service times” (mean cycle times of the output state machines, in isolation). 2.1. FRT-nets and subclasses 83 Note that in the case of totally open deterministic systems of sequential processes composed by two state machines, if (i) and (ii) of theorem 2.1.19 hold then the marking of all the buffers can be always computed from the marking of one buffer and the marking of the state machines. With the object of computing ergodicity conditions for a larger system including Nas a subsystem, if (i) and (ii) hold, from the performance point of view, we can suppose without loss of generality that the two state machines are communicating with at most one buffer. Let us now give the “transitivity rule” for three state machines communicating with buffers like in figure 2.13. This rule completes the stating of necessary and sufficient conditions for the existence of a Markovian timing that makes marking ergodic a given totally open deterministic system of sequential processes. Theorem 2.1.20 Let N,M 0=P1∪P2∪P3∪{b1,b 2,b 3},T 1∪T2∪ T3, Pre, Post, M0be a totally open deterministic system of sequential processes composed by three state machines and three buffers such that •b1⊆T1,b • 1⊆T3,•b2⊆T1,b • 2⊆T2,•b3⊆T2, and b• 3⊆T3. Then, there exists a Markovian interpretation making marking ergodic the system iff: i) Nis consistent and ii) (•b1,•b2)∈SDR,(b• 2,•b3)∈SDR,(b• 1,b • 3)∈SDR. Proof. If (•b1,•b2)∈ SDR or (b• 2,•b3)∈ SDR or (b• 1,b • 3)∈ SDR then the marking of b1and b3cannot be linearly expressed the one in function of the other. Then, these buffers have non-equal arrival rates, joint by a unique server (the state machine). Thus, the underlying Markov chain is transient or null recurrent, but never positive recurrent. Therefore, it is marking non-ergodic. Now, let us suppose that (i) and (ii) hold. (b• 2,•b3)∈SDR implies that b2,N2,M 0|2=P2,T 2,Pre|2, Post|2,M 0|2, and b3 can be substituted by a unique buffer without changing the behaviour of N1,M 0|1=P1,T 1,Pre|1, Post|1,M 0|1and N3,M 0|3= P3,T 3,Pre|3, Post|3,M 0|3. Then, if the net is consistent, (•b1,•b2)∈ SDR and (b• 1,b • 3)∈SDR, and theorem 2.1.19 can be applied. 84 CHAPTER 2. Petri net subclasses and qualitative theory If (i) and (ii) of theorem 2.1.20 hold, then the marking of b3can be always computed from the marking of b1,b 2and the marking of the state machines. As an example, let as consider the system depicted in figure 2.13. It verifies conditions (i) and (ii) of theorem 2.1.20. And it can be easily checked that: M(b3)=M(b1)+M(p2 1)+M(p2 3)−M(b2)− M(p1 2), for all marking M, reachable from the initial marking. With the object of computing conditions for a larger system including Nas a subsystem, if (i) and (ii) hold, the state machine M2and the buffers b2,b 3can be substituted by a unique buffer. Theorems 2.1.19 and 2.1.20 provide rules for an iterative reduction of buffers of a totally open deterministic system of sequential processes. These rules preserve the possibility of existence of a Markovian timing that makes the system marking ergodic if the necessary and sufficient conditions (stated in the mentioned theorems) hold. Therefore the existence of a Markovian timing that makes marking ergodic a totally open deterministic system of sequential processes is characterized in terms of pure structural conditions that can be checked in polynomial time: consistency and some global synchronic distance relations. 2.2 Persistent nets and behaviourally extended free choice nets Persistent nets [LR78] and behaviourally extended free choice nets (or “r´eseaux `a choix non-impos´e” [Bra83]) are recalled in this section as behaviourally defined net subclasses for which some reachability analysis is needed for the computation of the vector of visit ratios for transitions. Therefore, visit ratios do depend not only on the structure and routing but also on the initial marking. 2.2.1 Persistent nets Persistent nets [LR78] constitute a behaviourally characterized subclass of Petri nets which has a common property with live and bounded mono-T-semiflow nets: all their consistent firing count vectors are proportional to a unique vector, which is the unique minimal T-semiflow Chapter 3 Bounds for strongly connected marked graphs In this chapter, we obtain upper and lower bounds on the steady-state performance of marked graphs [CCCS89,CCCS90], a well-known subclass of Petri nets (see definition 2.1.10) that allow only concurrency and synchronization but no choice. In particular we derive bounds for the throughput of transitions (see definition 1.2.5), defined as the average number of firings per time unit (or its inverse, that we call the mean cycle time of transitions). From this quantity, applying Little’s formula [Lit61] it is possible to derive other average performance estimates of the model. Under these restrictions we will show results that can be computed in polynomial time on the size of the net model, and that depend only on the mean values and not on the higher moments of the probability distribution functions of the random variables that describe the timing of the system. The independence of the probability distribution can be viewed as a useful generalization of the performance results, since higher moments of the service delays are usually unknown for real cases, and difficult to estimate and assess. Moreover we show that both upper and lower bounds, computed by means of proper linear programming problems, are tight, in the sense that for any marked graph model it is possible to define families of stochastic timings such that the steady-state performances of the timed Petri net models are arbitrarily close to either bound. Figure 3.1 depicts an example of a live and 1–bounded marked 91 F J N=1 p1 p2 p3p5 p4 t1 t2 t3 t4 92 CHAPTER 3. Bounds for strongly connected marked graphs Figure 3.1: Example of a 1–bounded marked graph and its synchronized queueing network counterpart. graph. In the same figure the equivalent representation in terms of queueing network with synchronization primitives [SMK82] is also depicted. According to figure 3.1, Petri net places correspond with queues, while net’s transitions represent servers and synchronization constraints. It is easily seen that only sum and “max” operators are needed to compute the performance: indeed the actual cycle time in this example is the random variable γ=τ1+ max{τ2,τ 3}+τ4(where τidenotes the enabling time of transition ti, or its service time, with queueing networks terminology), therefore the mean cycle time is Γ=E[γ]=E[τ1]+E[max{τ2,τ 3}]+E[τ4]=s1+E[max{τ2,τ 3}]+s4 (3.1) where sidenotes the average enabling time of transition ti, i.e., its average service time. Cohen et al. developed a special algebra to formalize the properties of this kind of models in the deterministic case [CMQV89]. F. Baccelli et al. extended this approach to the stochastic case [BM89,BBW89]. Our idea is that of computing fast bounds for the throughput of transitions based only on the knowledge of the first moments of probability distribution functions. This can be intuitively explained as follows. The sum is independent of the probability distribution 3.0. Upper bound on throughput 93 (for linearity); since for non-negative variables xi≤maxi{xi}≤ ixi,E[maxi{xi}] can be bounded by maxi{E[xi]}≤E[maxi{xi}]≤ iE[xi]. Therefore for the net in figure 3.1 we can write: s1+ max{s2,s 3}+s4≤Γ≤s1+s2+s3+s4(3.2) In this chapter, we show how linear programming problems based on the incidence matrix of the underlying Petri net structure can be solved to compute this kind of bounds for marked graphs. In section 3.1, we focus our attention on throughput upper bounds for strongly connected marked graphs. Applying Little’s formula [Lit61] to each place of the net and using structural information taken from P-semiflows, a linear programming problem is derived whose optimum solution (which can be computed in polynomial time) is a lower bound for the mean cycle time of transitions (inverse of the average throughput). Moreover, this bound is shown to be reachable for arbitrary net structure, initial marking, and mean and variance for transition service times. From the linear programming form of the computed bound, some interesting results are derived. A tight lower bound for the steady-state throughput (upper bound for the mean cycle time) is obtained in polynomial time in section 3.2, from the knowledge of the given average service times and the liveness bounds of transitions, which are computed by solving proper linear programming problems. This bound cannot be improved unless more information from the service times of transitions than their mean values are used. The case of non-strongly connected (i.e., unbounded) marked graphs is considered in section 3.3. For these nets, the exact throughput of transitions can be derived from the knowledge of the exact throughput of the isolated strongly connected components. Since we are able to compute bounds for the throughput of the isolated strongly connected components, bounds for the whole net can be obtained. Finally, in section 3.4, some concluding remarks are presented. 94 CHAPTER 3. Bounds for strongly connected marked graphs 3.1 Upper bound for the steady-state throughput In this section, upper bounds on throughput for strongly connected (and thus structurally bounded, by property 2.1.13) marked graphs are presented. We remark that strong connectivity of a graph is a wellknown problem of polynomial time complexity. 3.1.1 Little’s law and P-semiflows Three of the most significant performance measures for a closed region rof a network in the analysis of queueing systems are related by Little’s formula [Lit61], which holds under very general (i.e., weak) conditions: Qr=XrRr(3.3) Qris the average number of customers in the region, Xris the output rate (throughput) from the region (which is equal to the input rate), and Rris the average time spent by a customer within the region. Now, Little’s result is applied to each place of a weakly ergodic net. Denoting as M(pi) the limit average number of tokens at place pi,X the limit vector of transition throughputs (see definition 1.2.5), and R(pi) the average time spent by a token within the place pi(average response time at place pi), the above mentioned relationship is stated as follows (see [FN85a]): M(pi)=(PRE[pi]·X)R(pi)(3.4) where PRE[pi]istheith row of the pre-incidence matrix of the underlying Petri net, thus PRE[pi]·Xis the output rate of place pi. In the study of computer systems, Little’s law is frequently used when two of the related quantities are known and the third one is needed. This is not exactly the case here. Now, R(pi) and M(pi) are unknown. On the other hand, the vector of visit ratios v(j)=1 X(tj)X=Γ (j)X(3.5) 3.1. Upper bound on throughput 95 normalized for having the jth component equal 1, can be easily computed for important net subclasses (see chapter 2) and, in particular, for live marked graphs. Γ(j)is called mean cycle time of transition tj (inverse of its average throughput). The average response times at places R(pi) are unknown. In fact, they can be expressed as sums of the average waiting times due to the synchronization schemes and the average service times associated with transitions, and only average service times are known: si,i= 1,...,m. Thus the average response times can be lowerly bounded from the knowledge of the average service times, and the following system of inequalities can be derived from (3.4): Γ(j)M≥PRE · D(j)(3.6) where  D(j)is the vector with components D(j) i=v(j) isi, average service demand (or loading) for each transition tiof the net, that is the average total service that a token demands from transition tiin all its visits to it. The superscript “(j)” indicates that the vector is normalized for having the jth component D(j) jequal to sj(i.e., v(j) i= 1). Since marked graphs are consistent nets and their unique minimal T-semiflow is 11, we have v(j)=11=v for all transition tj(cfr. property 2.1.12), thus for all j=1,...,m,Γ (j)=Γ,  D(j)= D=s (where s denotes the vector with components si,i=1,...,m), and ΓM≥PRE ·s (3.7) From this inequality, a lower bound Γmin for the mean cycle time of transitions can be derived. We take into account that Γmin must be such that inequality (3.7) holds and for some place pithe equality is reached: Γmin =PRE[pi]·s M(pi)(3.8) Since the vector Mis unknown, (3.8) cannot be solved. However, the following structural marking invariant can be written using a Psemiflow Y: YT·M0=YT·M=YT·M, ∀M0∈IN n,∀M∈R(N,M 0)(3.9) 96 CHAPTER 3. Bounds for strongly connected marked graphs Now, from (3.7) and (3.9): Γ(YT·M0)≥YT·PRE ·s (3.10) And a lower bound for the mean cycle time in steady-state is: Γmin = max Y∈{P−semiflow} YT·PRE ·s YT·M0 (3.11) Of course, an upper bound for the throughput of transitions is 1/Γmin. Let us formulate the previous lower bound for the mean cycle time in terms of a particular class of optimization problems called fractional programming problems [Mur83]: Γmin = maximize YT·PRE ·s YT·M0 subject to YT·C=0 11T·Y>0 Y≥0 (3.12) The above problem can be rewritten as follows: Γmin = maximize YT·PRE ·s q subject to YT·C=0 11T·Y>0 YT·M0=q Y≥0 (3.13) Then, because YT·M0>0 (guaranteed for live marked graphs, by corollary 2.1.7), we can change Y qby Yand obtain the linear programming formulation stated in the next theorem (in which 11T·Y>0is removed because YT·M0= 1 implies 11T·Y>0): 3.1. Upper bound on throughput 97 Theorem 3.1.1 A lower bound for the mean cycle time for live strongly connected marked graphs can be obtained by solving the following linear programming problem: Γmin =maximize YT·PRE ·s subject to YT·C=0 YT·M0=1 Y≥0 (LPP3) The following theorem concerns a special class of optimum solutions of (LPP3) that will be used later in the interpretation of this linear programming problem: the minimal P-semiflows. Firstly, we present a lemma that will be used in the proof of the theorem. Lemma 3.1.1 [MS82] Let Nbe a Petri net and Cits incidence matrix. A P-semiflow Yof Nis minimal iff the cardinal of its support is one unit higher than the rank of the submatrix made up of the rows liof C such that Y(i)is not zero. In order to prove the theorem, we use the concept of basic feasible solution from linear programming [Mur83], and the problem (LPP3) rewritten in the following way: Γmin = maximize YT·PRE ·s subject to YT·[C|M0]=(0|1) Y≥0 (LPP4) Let Ybe the set of feasible solutions of (LPP4). If Y∈Y, the set of row vectors of A=[C|M0] that Yuses is {A[j]|jis such that Y[j]>0}. The feasible solution Y∈Yis said to be a basic feasible solution for (LPP4) iff the set of row vectors of Athat Yuses is a linearly independent set. Theorem 3.1.2 Under the conditions of theorem 3.1.1, if (LPP3) has an optimum solution, then it has an optimum solution which is a minimal P-semiflow. Proof. Taking into account [Mur83, theorem 3.3], if (LPP4) has an optimum feasible solution, then it has a basic feasible solution Ythat 98 CHAPTER 3. Bounds for strongly connected marked graphs is optimum. Therefore, the set of rows that are used by Yis linearly independent (i.e., full rank). Considering that YT·C= 0, the number of non-null entries of vector Y(i.e., the number of rows used by Y)is equal to the rank of rows of Cused by Yplus one. This last statement is precisely the characterization of a minimal P-semiflow, presented in lemma 3.1.1. It is well-known that the simplex method for the solution of linear programming problems gives good results in practice, even if it has exponential worst case complexity. In any case, an algorithm of polynomial worst case complexity can be found in [Kar84]. Theorem 3.1.1 shows that the problem of finding an upper bound for the steady-state throughput (lower bound for the mean cycle time) in a strongly connected stochastic marked graph can be solved looking at the mean cycle time associated with each P-semiflow (circuits for marked graphs, see theorem 2.1.6) of the net, considered in isolation. These cycle times can be computed making the summation of the average enabling times of all the transitions involved in the P-semiflow (service time of the whole circuit), and dividing by the number of tokens present in it (customers in the circuit). 3.1.2 Reachability of the upper bound The above bound that holds for any stochastic interpretation, happens to be the same that has been obtained for strongly connected deterministically timed marked graphs by other authors (see for example [Ram74,RH80]), but here it is considered in a practical linear programming form. For deterministically timed nets, the reachability of this bound has been shown [Ram74,RH80]. Since deterministic timing is just a particular case of stochastic timing, the reachability of the bound is assured for our purposes as well. Even more, the next result shows that the previous bound cannot be improved only on the base of the knowledge of the coefficients of variation for the transition service times. Theorem 3.1.3 For live strongly connected marked graphs with arbitrary values of mean and variance for transition service times, the 3.1. Upper bound on throughput 99 lower bound for the mean cycle time obtained from (LPP3) cannot be improved. Proof. We know from [Ram74] that for deterministic timing the bound is reached. Only “max” and sum operators are needed to compute the cycle time. Therefore we must construct a family of random variables with arbitrary means and variances behaving in the limit like deterministic timing for both operators (max and sum). This is the case for the following family of random variables, for varying values of the parameter α∈[0,1): Xsi,σi(α)=siαwith probability 1 −i si(α+1−α i) with probability i(3.14) where i=s2 i(1 −α)2 s2 i(1 −α)2+σ2 i (3.15) These variables are such that E[Xsi,σi(α)] = si,Var[Xsi,σi(α)] = σ2 i, and they verify: lim α→1E[max{Xsi,σi(α),X sj,σj(α)}] = max{si,s j}(3.16) and, of course, for all αsuch that 0 ≤α<1: E[Xsi,σi(α)+Xsj,σj(α)] = si+sj. Then, if random variables Xsi,σi(α) are associated with transitions ti,i=1,...,m, taking αcloser to 1, the mean cycle time tends to the bound given by (LPP3). A polynomial computation of the minimal cycle time for deterministically timed strongly connected marked graphs was proposed in [Mag84], solving the following linear programming problem: Γmin = minimize γ subject to −C·z+γM0≥POST ·s γ, z ≥0 (LPP5) 100 CHAPTER 3. Bounds for strongly connected marked graphs To investigate the relationship between (LPP3) and (LPP5) let us consider the dual problem [Mur83] of (LPP5): Γmin = maximize YT·POST ·s subject to YT·C≤0 YT·M0≤1 Y≥0 (LPP6) Since strongly connected marked graphs are conservative (property 2.1.13), there does not exist Y≥0 such that YT·C≤ /0 and then the constraint YT·C≤0 of (LPP6) becomes YT·C= 0 (i.e., the constraint of (LPP3)). For all Ysuch that YT·C=0: YT·POST =YT·PRE. For live marked graphs, ∀Y∈IN n,Y= 0 such that YT·C= 0 then YT·M0≥1 (corollary 2.1.7). Thus the constraint YT·M0≤1 of (LPP6) becomes YT·M0= 1 for live nets (i.e., the constraint of (LPP3)). Hence for live strongly connected marked graphs, the problem (LPP3) is equivalent to (LPP5) formulated in [Mag84] for deterministic systems. 3.1.3 Interpretation and derived results Linear programming problems give an easy way to derive results and interpret them. Just looking at the objective function of the problem (LPP3) the following monotonicity property is obtained: the lower bound for the mean cycle time does not increase if s decreases or if M0 increases. Property 3.1.1 Let N,M 0be a live strongly connected marked graph and s the vector of average service times. 1. For a fixed s,ifM 0≥M0(i.e., increasing the number of initial resources) then the lower bound for the mean cycle time of N,M 0,sis less than or equal to the one of N,M 0,s(i.e., Γmin≤Γmin). 2. For a fixed M0,if s≤s (i.e., for faster resources) then the lower bound for the mean cycle time of N,M 0, sis less than or equal to the one of N,M 0,s(i.e., Γmin≤Γmin). p1 p2p3 p5 p4 t1 t2t3 t4 p1 p2p3 p5 p4 t1 t2t3 t4 p6 p1 p3 p5 p4 t1 t2t3 t4 p6 a) Original net with t and t concurrent. 2 3 b) Transformed net: t and t sequentialized and p made implicit. 2 2 3 c) Elimination of implicit places. Main loop: p , p , p , p . Minor cycle: p , p , p . 1 1 3 3 4 5 6 3.2. Lower bound on throughput 107 Figure 3.2: Example of structural sequentialization. An example of application of the lemma follows, in order to clarify the procedure. Consider the net depicted in figure 3.2.a. This net contains only two cycles, namely t1,t 2,t 4, and t1,t 3,t 4; we can then add either the cycle t1,t 2,t 3,t 4or t1,t 3,t 2,t 4; figure 3.2.b depicts the resulting net in case we choose to add the second cycle. In this case only place p6(from t3to t2) needs to be added to obtain the longer cycle, and it should be marked with one token, so that the new cycle comprising places p1,p 3,p 6,p 4contains two tokens, as the original cycle p1,p 2,p 4(while the other original cycle p1,p 3,p 5contained only one). In our example, we need not to iterate the procedure since we already have obtained a cycle containing all transitions of the marked graph. At this point we can identify and eliminate the implicit places that have been created during the cycles interleaving procedure. In the present example, we can easily see that place p2becomes implicit in figure 3.2.b, so that it can be removed, finally leading ourselves to the marked graph depicted in figure 3.2.c. It should be evident that the marked graph transformed by applying the above lemma has a mean cycle time which is greater than or equal to the mean cycle time of the original one, since some additional con- 108 CHAPTER 3. Bounds for strongly connected marked graphs straints have been added to the enabling of transitions: hence the mean cycle time of the transformed marked graph is a lower bound for the performance of the original one. Now if NM= maxt∈TL(t) = 1 in the above lemma, we re-find the lower bound of theorem 3.2.1. In the case of NM>1 we can show that the mean cycle time of the transformed net cannot exceed Γmax of equation 3.21 as follows. Theorem 3.2.2 For any live and bounded marked graph with a specification of the average service time sjfor each transition tjit is not possible to assign probability distribution functions to the transition service times such that the mean cycle time is greater than Γmax = m  j=1 sj L(tj)(3.22) independently of the topology of the net (and thus independently of the potential maximum degree of parallelism intrinsic in the marked graph). Proof. Without loss of generality, assume that transitions in the net resulting from the application of lemma 3.2.1 are partitioned in two classes C2and C1, with liveness bounds K2=NM>1 and K1<N M, respectively (the proof is easily extended to the case of more than two classes). Construct a new model containing only K1tokens in the main cycle; at this point all transitions behave as K1–servers, so that the mean cycle time is given by the sum of the firing times of all transitions, divided by the total number of customers in the main loop K1; moreover the delay time for the transitions belonging to class C1is simply given by S1=tj∈C1sj. Now if we increase the number of tokens in the main loop from K1to K2, the delay time of C1cannot increase, so that the contribution of C1to the mean cycle time cannot exceed S1for each of the first K1tokens. Under the hypothesis that the throughput of the system is given by the inverse of Γmax (i.e., assuming X=1/Γmax), the average number of tokens of the main loop computed using Little’s formula cannot exceed N1=XS1, therefore the average number of tokens available to fire transitions in C2cannot be lower than N2=K2−N1=K2 K2−K1 K1tj∈C1sj+tj∈C2sj tj∈C2sj+K2 K1tj∈C1sj (3.23) 3.2. Lower bound on throughput 109 On the other hand, we need only N2=XS2=K2 S2 tj∈C2sj+K2 K1tj∈C1sj (3.24) tokens to sustain throughput Xin subnet C2, so that we are assuming a delay in C2 S2≤K2−K1 K1 tj∈C1 sj+ tj∈C2 sj(3.25) Now we claim that this is the actual maximum delay because the first K1tokens can proceed at the maximum speed in the whole net, thus experiencing only delay tj∈C2sjin subnet C2, while the remaining K2−K1tokens can also queue up for travelling through C1,thus experiencing an additional delay of 1 K1tj∈C1sjeach. Now, taking into account that the liveness bound of a transition of a net Ndoes not change in the reverse net N−1, an analogous result to property 3.1.3 for the lower bound on throughput can be derived. Property 3.2.1 Let Nbe a strongly connected marked graph and N−1 its reverse net. Then, the lower bounds on throughput obtained for both nets as in theorem 3.2.2 are the same. 3.2.3 Reachability of the lower bound The lower bound in performance given by the computation of 1/Γmax as defined in theorem 3.2.2 can be shown to be reachable for any marked graph topology and for some assignement of probability distribution functions to the service time of transitions, exploiting the reachability of the trivial bound shown in theorem 3.2.1 for 1–live marked graphs. Theorem 3.2.3 For any strongly connected marked graph with a specification of the average service time sjfor each transition tj, and for all 0<≤1, it is possible to assign probability distribution functions to the transition service times such that the mean cycle time is: Γmax = m  j=1 sj L(tj)−O()(3.26) 110 CHAPTER 3. Bounds for strongly connected marked graphs independently of the topology of the net (and thus independently of the potential maximum degree of parallelism intrinsic in the marked graph). Proof. By construction, in a very similar way than in the case of theorem 3.2.1. The only technical difference is that now, without any loss of generality, we assume first of all to enumerate transitions in non-increasing order of liveness bound, i.e., rename the transitions in such a way that ∀ti,t j∈T,i>j =⇒L(ti)≤L(tj). Then, as in the case of theorem 3.2.1, we can show that the association of the family of random variables xj−1 sj() with each transition tj∈Tyields exactly the mean cycle time Γmax claimed by the theorem. To give the proof we consider a sequence of models ordered by the index of transitions, in which the qth model of the sequence has transitions t1,t 2,...,t qtimed with the random variables xj−1 sj(), and all other transitions immediate (firing in zero time); the |T|th model in the sequence represents the resulting model that is expected to provide the example of reachability of the lower bound. By induction we prove that the qth model in the sequence has a mean cycle time Γq= q  j=1 sj L(tj)−O()(3.27) Base: q= 1: Trivial since the repetitive cycle that constitute the steady-state behaviour of the marked graph contains only one (L(t1)– server) deterministic transition with average firing time Γ1=s1/L(t1). Induction step: q>1: Taking the limit →0, each server of the newly timed transition tqwill fire most of the times with time zero, thus normally not contributing to the computation of the mean cycle time, that will be just Γq−1= q−1  j=1 sj L(tj)−O()(3.28) (as in the case of model q−1) with probability 1 −q−1. On the other hand, each of the servers of the newly timed transition has a (very small) probability q−1of delaying its firing of a time sq/q−1, which is at least order of 1/ bigger than any other firing time in the cycle. Now if L(tq) = 1, then the proof is completed, since also ∀j>q, 3.2. Lower bound on throughput 111 L(tj) = 1 by hypothesis, and we reduce to the induction step of the proof of theorem 3.2.1. Instead if L(tq)>1 then we can consider L(tq) consecutive firings of tq, and compute the average firing time as the total time to fire L(tq) times the transition, divided by L(tq). Now if we consider mconsecutive firings of instances of transition tqwe obtain an average delay: m−1  j=0 (1 −q−1)j(q−1)(m−j)(m−j)sq (q−1) =sq(1 + O()) (3.29) Therefore the mean cycle time of the qth model will be Γq=(1−O(q−1))Γq−1+sq L(tq)(1+O()) = q  j=1 sj L(tj)−O().(3.30) 3.2.4 A polynomial algorithm to compute the lower bound First of all we recall (cfr. property 2.1.14) that in the case of live marked graphs the liveness bound equals the enabling and the structural enabling bounds for each transition; thus we present a characterization of the problem of the determination of the structural enabling bound in terms of a linear programming problem, which is known to be solvable in polynomial time. For any transition t∈T, the computation of the structural enabling bound SE(t) is formulated in definition 1.2.3, in terms of problem (LPP1). In that problem we can observe that the vector Mis redundant in the system of linear inequalities, so that we can remove it, obtaining: SE(t) = maximize k subject to M0+C·σ ≥kPRE[t] M0+C·σ ≥0,σ≥0 (LPP9) Alternatively, we can switch to the dual linear programming problem: 112 CHAPTER 3. Bounds for strongly connected marked graphs SE(t) = minimize YT·M0 subject to YT·C≤0 YT·PRE[t]=1 Y≥0 (LPP10) Marked graphs are consistent nets with a single minimal T-semiflow which is the vector 11 (property 2.1.12), so that the constraint σ ≥0 can be relaxed in the primal problem. The effect on the dual problem of this relaxation is the transformation of the first constraint into YT·C=0. In other words, the dual problem for the computation of SE(t) can be rewritten as follows: SE(t) = minimize YT·M0 subject to YT·C=0 YT·PRE[t]=1 Y≥0 (LPP11) This linear programming problem is less complex to solve with the simplex algorithm than the original dual problem because it involves the introduction of fewer slack variables. For all strongly connected marked graph there exists an elementary P-semiflow for which the optimum of the objective function is achieved, as shown in theorem 3.1.2. In case of marked graphs, these elementary P-semiflows can only be elementary cycles, so that we can give the following interpretation of the linear programming problem (LPP11) in net terms: the liveness bound for a transition tof a strongly connected marked graph is given by the minimum number of tokens contained in any cycle of places containing transition t. In a non-strongly connected marked graph there can be no such cycle, so that this number can be infinite. As final remarks we can state the following: Property 3.2.2 Let N,M 0be a marked graph. 1. Liveness for N,M 0can be a byproduct of a more general (polynomial complexity) computation: N ,M 0is a live marked graph if and only if for all transition t,SE(t)>0. t1t2 t3 t4 t5 p1 p2 p3 p4 p5 p6 (a) t1t2 t4 t5 p1 p2 p34 p5 p6 (b) (c) p3 p4 T3 T12 T45 3.2. Unbounded marked graphs 113 Figure 3.3: Non-strongly connected marked graphs. 2. If N,M 0is live and ∃t∈Tsuch that SE(t)=1, then ∀t∈T belonging to the same cycle denoted by Yin (LPP11), SE(t)=1. Note that the application of property 3.2.2.2 reduces the computational complexity of the structural enabling bound of all transitions. 3.3 Extending results to unbounded marked graphs In the literature on deterministically timed marked graph models the case of non-strongly connected nets is usually considered a trivial extension to be left to the imagination of the reader [RH80,Mag84]. In this section we argue that the question is less trivial than one can perceive at first glance, and in fact we shall derive some examples that show that “direct” extensions of the results obtained in the case of strongly connected marked graphs, in general, make no sense. In fact, for the upper bound on throughput, we obtain a result similar to that proposed by F. Baccelli et al. [BBW89], even though their work is situated in a quite different framework. Example 1. Let us first consider as an example the non-strongly connected marked graph in figure 3.3.a. First of all we can see that 114 CHAPTER 3. Bounds for strongly connected marked graphs transition t3has an infinite liveness bound, so that in steady-state it should not contribute to the computation of the mean cycle time. Indeed, suppose that t3has a deterministic service time of 1000 time units, while transitions t1and t2have a deterministic service time of 1 time unit; thus the cycle t1–t2starts generating tokens at a rate of one token every 2 time units, so that initially tokens accumulate in place p3. At time 1001 eventually the first instance of transition t3 fires, and at that point we reach the steady-state condition in which 499 instances of firing of t3are concurrently enabled, with a remaining enabling time shifted of two time units between each pair of subsequent firing instances. As we can see, the actual firing rate in steady-state for transition t3is 1/2 firings per second, i.e., it is determined by the mean cycle time of transitions t1–t2completely independent of the service time of t3itself. Therefore, from the steady-state performance point of view, transition t3behaves as if it were an immediate transition, and it can be reduced by fusing places p3and p4into a single place p34,as shown in figure 3.3.b. Now let us consider the behaviour of the other two transitions t4and t5. Their actual firing rate is determined both by their own service times and the rate with which the cycle t1–t2is able to produce the tokens that are consumed by t4from place p34. Thus the mean cycle time in steadystate condition for transitions t4–t5is given by the maximum between the mean cycle time of t1–t2and the sum of the service times of t4and t5(this sum would be the mean cycle time of the subnet generated by t4and t5if it were considered in isolation, i.e., the potential mean cycle time of t4–t5). In the case in which the mean cycle time of t1–t2were greater than the one of t4–t5, the number of tokens at place p34 would remain bounded and the firing rate of t4–t5would be the inverse of the mean cycle time of t1–t2. On the other hand, in the case in which the mean cycle time of t1–t2were less than the one of t4–t5, place p34 would accumulate tokens and marking process of this place would not be (even weakly) ergodic. However, firing rate of transitions t4–t5would be, in that case, equal to the inverse of their potential mean cycle time. In the case of equality between mean cycle time of t1–t2and t4–t5, marking ergodicity at place p34 depends on the probability distribution of service time of transitions. In the particular case of deterministic timing, the marking process is weakly ergodic, while in the case of exponentially p1 p2p3p6 p5 p4 p7p10 p11 p8 p9p12 t1t2t3t4 t5 t6t7t8t9 (a) (b) p3p6 p7p10 T12 T34 T5 T67 T89 3.3. Unbounded marked graphs 115 Figure 3.4: A more general non-strongly connected marked graph. distributed service times the marking process is non-ergodic (because the embedded Markov process is null-recurrent). Example 2. Let us consider the more general example shown in figure 3.4.a. Also in this case it is easy to understand that transition t5 gives no contribution to the steady-state cycle time because it has an infinite liveness bound (it behaves as an immediate transition). However in this case we cannot just delete it because of the synchronization constraint that is due to its multiple input places (p3and p6). On the other hand, it is clear that the two subnets composed of t1–t2and t3–t4behave completely independently of each other and of the rest of the net. If the mean cycle times of these two subnets are not exactly equal (let us assume without loss of generality that the mean cycle time of t1–t2is greater than that of t3–t4), then one of the input places of t5(p6with our assumption) accumulates an infinite number of tokens in steady-state (in other words, the marking process at this place is not ergodic); thus it becomes redundant (in steady-state) since it cannot constraint the enabling condition of t5, and it can be deleted without altering the behaviour of the net. In the case of exactly equal mean cycle times of the two subnets (t1–t2and t3–t4), marking ergodicity depends on the distribution functions associated with transitions. For instance, for deterministic timing the marking process at p3and 116 CHAPTER 3. Bounds for strongly connected marked graphs p6remains bounded (i.e., it is weakly ergodic). On the other hand, for exponential timing, the marking of both places is a null-recurrent Markov process, thus non-ergodic. Deleting all the places that become unbounded in steady-state due to the average transition firing times, we obtain that the net is partitioned in disconnected subnets that can be studied independently of one another. Of course, not only the input but also the output places of t5(p7and/or p10) may accumulate an infinite number of tokens in steady-state, provided that the potential mean cycle times of their output transitions (respectively, t7and t8) are greater than the actual firing time of t5. In this case, also the output places become redundant and can be deleted, and we may study the steady-state behaviours of the four disconnected subnets in isolation. From the analysis of the above examples we can draw two considerations. First: Marking ergodicity is not assured in the case of non-strongly connected marked graphs. Places having non-ergodic marking process can be found among structurally unbounded places (places do not belonging to any strongly connected component) in two cases: (1) after the comparison between the actual input firing rate and the potential firing rate of the output strongly connected component (example 1), or (2) after the comparison among the actual firing rate of all strongly connected components being synchronized by a given transition (example 2). In other words, strongly connected components of the marked graph can be seen as producers of parts (or data) for other components and consumers of parts that are produced by other components. Connections among these producers/consumers are modelled by means of places (or buffers). A place is marking ergodic if the throughput of the corresponding producer is less than the service rate of the consumer. Second: There exists a partial order relation “” among subsets of transitions defined as TiTjiff the firing delay of transitions in Tican affect the actual firing rate of transitions in Tjbut not vice versa. This partial order relation can be computed by applying a standard algorithm for the derivation of a condensation of the original net, as we explain below. Chapter 4 Bounds for live and bounded free choice nets The results presented in this chapter (that include part of those in [CCS90a] and [CCS90b]) are an extension to live and bounded free choice nets (see definition 2.1.11) of the performance bounds for strongly connected marked graphs developed in the previous chapter. The idea is that several consistent firing count vectors can be reproduced in steady-state, but decisions, freely done at certain places, are completely governed by the stochastic interpretation (in particular, by the routing rates) of the net, and the vector of visit ratios for transitions can be defined independently of the marking and the service times (see section 2.1). In section 4.1 we focus our attention on throughput upper bounds for live and bounded free choice nets. Using Little’s law like in previous chapter and structural linear marking relations, linear programming problems are derived whose optimum solutions are lower bounds for the mean cycle time of transitions. These problems include structural information of the net by means of the (pre-, post-) incidence matrices. All parameters defining stochastic interpretation are summarized in the vector of average service demands for transitions (products of visit ratios by average service times), which can be efficiently computed for live and bounded free choice nets (see section 2.1). Lower bounds for the steady-state throughput are considered in section 4.2. These bounds are computed from the liveness bounds of 123 124 CHAPTER 4. Bounds for live and bounded free choice nets transitions (obtained from linear programming problems in the case of live and bounded free choice nets) and from the average service demands for transitions. The throughput upper bound is shown to be reachable for 1– bounded nets for some distribution functions of service times with arbitrary mean values and for some conflict resolution policy, with arbitrary long run rates. The lower bound on throughput is reachable for 1–bounded nets. 4.1 Upper bounds for the steady-state throughput The computation of upper bounds for the throughput of transitions, defined as the average number of firings per time unit, is consider in this section, for live and bounded free choice nets. In section 4.1.1, Little’s law and structural linear marking relations are applied for the derivation of linear programming problems, analogous to that presented in section 3.1. The bounds obtained using Psemiflows (section 4.1.1.2) can be improved taking into account other marking invariants derived from the concept of trap (section 4.1.1.3), or after the addition of some implicit places to the net (section 4.1.2). The bounds derived in sections 4.1.1 and 4.1.2 are non-reachable, in general. A reachable throughput upper bound for the case of 1– bounded nets is obtained in section 4.1.3. The idea is the following: a reachable bound for strongly connected marked graphs was computed in previous chapter using the circuits of the net. Such circuits can be interpreted in algebraic terms for marked graphs as elementary Psemiflows (see theorem 2.1.6.1). This is the reason why we try to derive bounds for free choice nets from P-semiflows in section 4.1.1.2. Other natural extension of circuits of marked graphs for the case of free choice nets can be found in the framework of graph theory: multisets of circuits. From this approach, a reachable throughput upper bound can be derived for 1–bounded nets. 4.1. Upper bounds on throughput 125 4.1.1 Little’s law and linear marking relations Let us recall the system of inequalities (3.6) presented in chapter 3: Γ(j)M≥PRE · D(j)(4.1) where Γ(j)is the mean cycle time of transition tj(i.e., the inverse of its throughput), Mis the vector of limit average markings, PRE is the pre-incidence matrix of the net, and  D(j)is the vector of average service demands for transitions, with components  D(j) i=v(j) isi,i=1,...,m. We remark that vector  D(j)can be efficiently computed for live and bounded free choice nets, if average service times siare given, because the vector of visit ratios v(j)can be derived for such nets by solving a linear system of equations (free choice nets are FRT-nets; therefore, theorem 2.1.2 can be used). A goal of this section is the computation of lower bounds for the mean cycle time of transitions, based on the inequality (4.1). Since the limit average marking Mis unknown, linear marking relations derived from the underlying net will be considered to achieve this goal: ZT·M≤k, ∀M∈R(N,M 0),with Z≥ \0(4.2) Linearity is required in the above relation because, taking into account the definition of the limit average marking, a similar inequality can be derived for M: ZT·M= lim τ→∞ 1 ττ 0ZT·Mudu ≤lim τ→∞ 1 ττ 0kdu=k(4.3) In this case, the (unknown) vector Mcan be substituted in (4.1), premultiplied by Z, obtaining: Γ(j)≥ZT·PRE · D(j) k(4.4) and so a lower bound for the mean cycle time of tj. An additional advantage can be taken of the use of linear relations, since this linearity will lead, in most cases, to polynomial complexity calculations, based on linear algebra and linear programming techniques. 126 CHAPTER 4. Bounds for live and bounded free choice nets 4.1.1.1 Structural linear marking relations Since the limit average marking Mis unknown, we can use the approximation given by linear relations verified by all reachable markings. A first family of linear marking relations is obtained considering those being structurally characterized. These are stronger conditions than those expressed by inequality (4.2) (behaviourally defined), but they provide easier and more efficient techniques for their manipulation. Structural linear marking relations can be expressed using the incidence matrix C of the net: YT·C=0,Y ≥0=⇒YT·M=YT·M0,∀M∈R(N,M 0),∀M0(4.5) YT·C≤ /0,Y ≥0=⇒YT·M≤YT·M0,∀M∈R(N,M 0),∀M0(4.6) YT·C≥ \0,Y ≥0=⇒YT·M≥YT·M0,∀M∈R(N,M 0),∀M0(4.7) Let us consider firstly the case of equality relation given by equation (4.5). Vectors Y≥0 verifying this equation are often called conservative components or P-semiflows (see section 1.2.2), and they have been used for the computation of throughput upper bounds for strongly connected marked graphs, in section 3.1.1, by premultiplying the inequality (4.1). The obtained results using P-semiflows as well as their limitations for the computation of reachable (i.e., tight) bounds for live and bounded free choice nets are summarized in the next section. Regarding structural linear inequality relations for the reachable markings of a marked Petri net, vectors Y≥0 verifying (4.6) could be considered. Premultiplying the linear state equation of the net by such vectors, the following sequence of inequalities is obtained for each sequence of successor markings, and for all initial marking M0: YT·M0≥···≥YT·Mi−1≥YT·Mi≥YT·Mi+1 ≥··· (4.8) Moreover, YT·C= 0 implies that there exists (at least) a transition tjsuch that YT·C[tj]<0, and if Mi[tjMi+1 then YT·Mi>YT·Mi+1 in the sequence of inequalities (4.8) (i.e., strict inequality). But in this case the net cannot be live (because if it was live then transition tj could be fired an infinite number of times, an infinite number of strict 4.1. Upper bounds on throughput 127 inequalities would appear in (4.8), and this is impossible if the initial marking is finite). Thus, linear inequalities of the form YT·C≤ /0 are not usefull for us. Non-negative vectors satisfying the inequality (4.7): ZT·C≥ \0 cannot be used directly for the substitution of Min (4.1) (because they give inequalities in the opposite direction). P-semiflows Ycould be considered such that Y−Z≥0, thus: (Y−Z)T·C=YT·C    0 −ZT·C≤ /0(4.9) But the existence of such vectors Y−Z≥0, (Y−Z)T·C≤ /0, is not possible for conservative nets (and structurally live structurally bounded nets are conservative; see, e.g., [Sil85]). Alternatively, other linear marking inequalities of the form YT Θ·M≥ 1, for all (non-transient) marking Mcan be derived considering vectors YΘ≥0 having a trap Θ as support. Traps are sets of places which remain marked once they have gained at least one token. This structural concept can be used to improve the throughput upper bound computed by means of Little’s law and P-semiflows, and will be explained later. 4.1.1.2 Little’s law and P-semiflows P-semiflows Yare non-negative left annullers of the incidence matrix C(i.e., YT·C=0,thusYT·M=YT·M0for all reachable marking M). Now, using relation (4.4), the following lower bound for the mean cycle time of a given transition tjcan be derived: Γ(j)≥max Y∈{P−semiflow} YT·PRE · D(j) YT·M0 (4.10) The previous lower bound can be formulated in terms of a fractional programming problem and later, after some considerations (see section 3.1.1), transformed into a linear programming problem: Theorem 4.1.1 For any net, a lower bound for the mean cycle time of transition tjcan be computed by the following linear programming 128 CHAPTER 4. Bounds for live and bounded free choice nets problem: Γ(j)≥ΓPS (j)=maximize YT·PRE · D(j) subject to YT·C=0 YT·M0=1 Y≥0 (LPP12) If the solution of the problem (LPP12) is unbounded, since it is a lower bound for the mean cycle time of transition tj, the non-liveness can be assured (infinite cycle time). If the visit ratios for all transitions are non-null, then  D(j)>0, and the unboundedness of the above problem implies that a total deadlock is reached by the net. This result has the following interpretation: if the problem (LPP12) is unbounded then there exists an unmarked P-semiflow, and the net is non-live (recall corollary 2.1.11). Corollary 4.1.1 The problem (LPP12) has unbounded solution iff ∃Y≥ \0such that YT·M0=0and YT·C=0. Moreover, if this occurs, the net is non-live. In order to interpret the result presented in theorem 4.1.1, let us consider the particular case of the state machine (see definition 2.1.12) depicted in figure 4.1.a. Assume that s1=1,s2=s3=0,s4=1, and s5= 2 are the average service times of t1,t2,t3,t4, and t5, respectively, and that routing rates solving the conflict at place p2are r2=r3=1/2 for the firing of transitions t2and t3. In this case, the vector of visit ratios for transitions is v(1) =(1,1/2,1/2,1/2,1/2)T, thus the vector of average service demands is  D(1) =(1,0,0,1/2,1)T. The unique elementary P-semiflow is Y1=(1,1,1,1)T, and it is such that YT 1·M0= 3. Therefore, the application of theorem 4.1.1 gives the value ΓPS (1) =(1+1/2+1)/3=0.8333. In fact, in this case the obtained value is the exact mean cycle time of transition t1, independently of the probability distribution of service times. As we remarked in chapter 1, state machines are the Petri net counterpart of classical queueing networks. Since we assume infinite server semantics for transitions, the net of figure 4.1.a is isomorphic to a queueing network with delay stations, and in this case the cycle time is easily obtained as the sum of all the p1 t1p2 t2 t3 p3 p4 t4 t5 p1 t1 p3 p4 t4 t5 p2 p5 p6 t2 t3 (a) (b) 4.1. Upper bounds on throughput 129 Figure 4.1: Queueing networks with: (a) only delay nodes and (b) delay and single-server nodes, represented by means of (a) a state machine and (b) a free choice net. average service demands divided by the number of customers, because no queueing takes place at any node. Now, let us consider the net of figure 4.1.b, in which stations represented by transitions t4and t5are single-servers instead of delay nodes (with queueing terminology) or, in other words, have their liveness bounds limited to one (with our notation). In this case, the elementary P-semiflows are Y1=(1,1,1,1,0,0)T,Y2=(0,0,0,0,1,0)T, and Y3=(0,0,0,0,0,1)T, with YT 1·M0=3,YT 2·M0= 1, and YT 3·M0= 1. Therefore, the problem (LPP12) gives the value ΓPS (1) = max{(1+1/2+1)/3,1/2,1}= max{0.8333,0.5,1}= 1, and its inverse, which is the throughput upper bound, is also 1. In a queueing theory framework, the obtained bound is known as the asymptotic throughput upper bound [Kle76,DB78] and is obtained as the minimum between (a) the bound computed assuming that no queueing takes place at any node (0.8333, in this case), and (b) the maximum throughput of the bottleneck station (transition t5in the figure) which cannot have an utilization rate greater than 1. In the general free choice nets case, the bound presented in theorem 4.1.1 can be interpreted as the maximum among the asymptotic bounds obtained for the isolated subnets generated by all the elemen- t1t2 t3t4 t5 p1 p2p3 p4p5 q1-q 130 CHAPTER 4. Bounds for live and bounded free choice nets Figure 4.2: The throughput upper bound given by (LPP12) is non-reachable. tary P-semiflows of the net. Linear programming problems give an easy way to derive results and interpret them. Just looking at the problem (LPP12) the following monotonicity property is obtained, analogous to that obtained for marked graphs (property 3.1.1). Corollary 4.1.2 Let N,M 0be a live and bounded free choice net and s the vector of average service times. i) For a fixed s,ifM 0≥M0(i.e., increasing the number of initial resources) then the lower bound for the mean cycle time of N,M 0,sis less than or equal to the one of N,M 0,s(i.e., ΓPS (j)≤ΓPS (j)). ii) For a fixed M0,if s≤s (i.e., for faster resources) then the lower bound for the mean cycle time of N,M 0, sis less than or equal to the one of N,M 0,s(i.e., ΓPS (j)≤ΓPS (j)). Performance monotonicity does not hold for non-free choice nets increasing the number of initial resources, as was shown with the live net in figure 2.6 (for which the addition of one token makes it non-live). For strongly connected marked graphs, the bound derived from theorem 4.1.1 has been shown to be reachable for arbitrary mean values and coefficients of variation associated with transition service times 4.1. Upper bounds on throughput 131 (theorem 3.1.3). Unfortunately, this is not the case for live and bounded free choice nets. Let us consider, for instance, the live and 1–bounded free choice net depicted in figure 4.2. Let s3and s4be the average service times associated with t3and t4, respectively. Let t1,t2, and t5be immediate transitions (i.e., they fire in zero time). Let q,1−q∈(0,1) be the routing probabilities defining the resolution of conflict at place p1. The vector of visit ratios normalized for t5is v(5) =(q,1−q,q,1−q,1)T(4.11) The elementary P-semiflows are Y1=(1,1,0,0,1)T Y2=(1,0,1,1,0)T(4.12) Then, applying the problem (LPP12) to this net, the following lower bound for the mean cycle time of transition t5is obtained: Γ(5) ≥max{qs3,(1 −q)s4}(4.13) while the actual cycle time for this transition is Γ(5) =qs3+(1−q)s4(4.14) independently of the higher moments of the probability distribution functions associated with transitions t3and t4. Therefore, the bound given by theorem 4.1.1 is non-reachable for the net in figure 4.2. In the next section, we consider other linear marking relations, derived from the structural concept of trap, that can be used to improve the bound of theorem 4.1.1. 4.1.1.3 Little’s law and traps A trap in a Petri net Nis a subset of places Θ ⊆Psuch that Θ•⊆•Θ. A well-known property of these structural elements is recalled below. Theorem 4.1.2 [Hac72] Let N,M 0be a marked Petri net and Θ∈P a trap. If Θis initially marked, then Θis marked throughout the net’s evolution. 132 CHAPTER 4. Bounds for live and bounded free choice nets This property can be expressed in algebraic terms considering the vector YΘassociated with a given trap Θ, and defined as YΘ(p)=χΘ(p), for all place p(we denote χΘthe characteristic function of the set Θ, i.e., χΘ(p)=1ifp∈Θ, and χΘ(p) = 0 otherwise). If YT Θ·M0≥1 then YT Θ·M≥1 for all marking Mreachable from M0. Now let us consider the vector YΘassociated with a given trap Θ of a net, and a P-semiflow Ysuch that Y−YΘ≥0 (it always exists for conservative nets). The following linear relation can be derived: (Y−YΘ)T·M≤YT·M0−1(4.15) for all marking Mreachable from M0(thus the same relation holds for M). Premultiplying inequality (4.1) by Y−YΘ, the following lower bound for the mean cycle time of a transition t1is derived: Theorem 4.1.3 For any net Nand for any trap Θof N, a lower bound for the mean cycle time Γ(j)of transition tjis given by: Γ(j)≥ΓΘ (j)=maximize (Y−YΘ)T·PRE · D(j) YT·M0−1 subject to YT·C=0 Y−YΘ≥0 YΘ(p)=χΘ(p),∀p∈P (4.16) In the next section we derive a linear programming problem for the computation of an improvement of the previous bound based on the concept of implicit place. Going back to the net in figure 4.2, the unique minimal trap different from the P-semiflows is Θ={p1,p 4,p 5}(4.17) Considering the P-semiflow Y=(2,1,1,1,1)T(4.18) we have Y≥YΘ=(1,0,0,1,1)T(4.19) Bibliography [AMBB+89] M. Ajmone Marsan, G. Balbo, A. Bobbio, G. Chiola, G. Conte, and A. Cumani. The effect of execution policies on the semantics and analysis of stochastic Petri nets. IEEE Transactions on Software Engineering, 15(7):832–846, July 1989. [AMBC84] M. Ajmone Marsan, G. Balbo, and G. Conte. A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems. ACM Transactions on Computer Systems, 2(2):93–122, May 1984. [AMBC86] M. Ajmone Marsan, G. Balbo, and G. Conte. Performance Models of Multiprocessor Systems. MIT Press, Cambridge, USA, 1986. [AMBCC87a] M. Ajmone Marsan, G. Balbo, G. Chiola, and G. Conte. Generalized stochastic Petri nets revisited: Random switches and priorities. In Proceedings of the International Workshop on Petri Nets and Performance Models, pages 44–53, Madison, WI, USA, August 1987. IEEE-CS Press. [AMBCC87b] M. Ajmone Marsan, G. Balbo, G. Chiola, and G. Conte. Modeling the software architecture of a prototype parallel machine. In Proceedings of the 1987 SIGMETRICS Conference, Banff, Alberta, Canada, May 1987. ACM. [AMBCD86] M. Ajmone Marsan, G. Balbo, G. Chiola, and S. Donatelli. On the product-form solution of a class of 235 236 BIBLIOGRAPHY multiple-bus multiprocessor system models. Journal of Systems and Software, 6(1,2):117–124, May 1986. [BB80] S. C. Bruell and G. Balbo. Computational Algorithms for Closed Queueing Networks. Elsevier Science Publishers B.V. (North Holland), New York, 1980. [BBW89] F. Baccelli, N. Bambos, and J. Walrand. Flow analysis of stochastic marked graphs. In Proceedings of the IEEE Conference on Decision and Control, 1989. [BCMP75] F. Baskett, K. M. Chandy, R. R. Muntz, and F. Palacios. Open, closed, and mixed networks of queues with different classes of customers. Journal of the ACM, 22(2):248– 260, April 1975. [Bes87] E. Best. Structure theory of Petri nets: The free choice hiatus. In W. Brawer, W. Reisig, and G. Rozenberg, editors, Advances in Petri Nets’86 - Part I, volume 254 of LNCS, pages 168–205. Springer-Verlag, Bad Honnef, Germany, February 1987. [BG85] S. C. Bruell and S. Ghanta. Throughput bounds for generalized stochastic Petri net models. In Proceedings of the International Workshop on Timed Petri Nets, pages 250–261, Torino, Italy, July 1985. IEEE-CS Press. [BM89] F. Baccelli and A. Makowski. Queueing models for systems with synchronization constraints. Proceedings of the IEEE, 77(1):138–161, January 1989. [Bra83] G. W. Brams. R´eseaux de Petri: Th´eorie et Pratique. T.1. th´eorie et analyse. Masson, Paris, 1983. In French. [BT81] A. Bertoni and M. Torelli. Probabilistic Petri nets and semi-Markov systems. In Proceedings of the 2nd European Workshop on Petri Nets, pages 59–78, Bad Honnef, Germany, September 1981. BIBLIOGRAPHY 237 [Buz73] J. P. Buzen. Computational algorithms for closed queueing networks with exponential servers. Communications of the ACM, 16(9):527–531, September 1973. [BV84] E. Best and K. Voss. Free choice systems have home states. Acta Informatica, 21:89–100, 1984. [CCCS89] J. Campos, G. Chiola, J. M. Colom, and M. Silva. Tight polynomial bounds for steady-state performance of marked graphs. In Proceedings of the 3rd International Workshop on Petri Nets and Performance Models, pages 200–209, Kyoto, Japan, December 1989. IEEE-CS Press. [CCCS90] J. Campos, G. Chiola, J. M. Colom, and M. Silva. Properties and performance bounds for timed marked graphs. Technical report, Dpto. de Ingenier´ıa El´ectrica e Inform´atica, Universidad de Zaragoza, Spain, July 1990. [CCS89] J. Campos, G. Chiola, and M. Silva. Properties and steady-state performance bounds for Petri nets with unique repetitive firing count vector. In Proceedings of the 3rd International Workshop on Petri Nets and Performance Models, pages 210–220, Kyoto, Japan, December 1989. IEEE-CS Press. [CCS90a] J. Campos, G. Chiola, and M. Silva. Properties and performance bounds for closed free choice synchronized monoclass queueing networks. Research Report GISIRR-90-2, Dpto. de Ingenier´ıa El´ectrica e Inform´atica, Universidad de Zaragoza, Spain, January 1990. [CCS90b] J. Campos, J. M. Colom, and M. Silva. Improving throughput upper bounds for synchronized queueing networks. Technical report, Dpto. de Ingenier´ıa El´ectrica e Inform´atica, Universidad de Zaragoza, Spain, June 1990. 238 BIBLIOGRAPHY [CCS90c] J. Campos, J. M. Colom, and M. Silva. Performance evaluation of repetitive automated manufacturing systems. In Proceedings of the Rensselaer’s Second International Conference on Computer Integrated Manufacturing, pages 74–81, Rensselaer Polytechnic Institute, Troy, New York, May 1990. IEEE-CS Press. [CCS90d] J. M. Colom, J. Campos, and M. Silva. On liveness analysis through linear algebraic techniques. In Proceedings of Design Methods Based on Nets, ESPRIT Basic Research Action 3148, W.G.3, Paris, France, June 1990. Deliverables covering the period June 1989 to June 1990. [CCS91] J. Campos, G. Chiola, and M. Silva. Ergodicity and throughput bounds of Petri nets with unique consistent firing count vector. IEEE Transactions on Software Engineering, February 1991. To appear. [Cha72] K. M. Chandy. The analysis and solutions for general queueing networks. In Proceedings of the Sixth Anual Princeton Conference on Information Sciences and Systems, pages 224–228, Princeton, NJ, USA, March 1972. [CHEP71] F. Commoner, A. Holt, S. Even, and A. Pnueli. Marked directed graphs. Journal of Computer and System Science, 5(5):511–523, October 1971. [Chi87] G. Chiola. A graphical Petri net tool for performance analysis. In Proceedings of the 3rd International Workshop on Modeling Techniques and Performance Evaluation, Paris, France, March 1987. AFCET. [CHW75] K. M. Chandy, U. Herzog, and L. S. Woo. Parametric analysis of queueing networks. IBM Journal of Res. Develop, 19(1):36–42, January 1975. [Cia89] G. Ciardo. Analysis of Large Stochastic Petri Net Models. PhD thesis, Department of Computer Science, Duke University, Durham, NC, 1989. BIBLIOGRAPHY 239 [CMQV89] G. Cohen, P. Moller, J. P. Quadrat, and M. Viot. Algebraic tools for the performance evaluation of discrete event systems. Proceedings of the IEEE, 77(1):39–58, January 1989. [Cou77] P. J. Courtois. Decomposability: Queueing and Computer System Applications. Academic Press, New York, 1977. [Cox55] D. R. Cox. A use of complex probabilities in the theory of stochastic processes. Proceedings of the Cambridge Philosophical Society, 51(2):313–319, April 1955. [CS89a] J. Campos and M. Silva. Steady-state performance evaluation of totally open systems of Markovian sequential processes. In M. Cosnard and C. Girault, editors, Decentralized Systems, pages 427–438. North-Holland, Amsterdam, 1990. [CS89b] J. M. Colom and M. Silva. Convex geometry and semiflows in P/T nets. A comparative study of algorithms for computation of minimal p-semiflows. In Proceedings of the 10th International Conference on Application and Theory of Petri Nets, pages 74–95, Bonn, Germany, June 1989. [CS89c] J. M. Colom and M. Silva. Improving the linearly based characterization of P/T nets. In Proceedings of the 10th International Conference on Application and Theory of Petri Nets, pages 52–73, Bonn, Germany, June 1989. [DA84] M. Diaz and P. Azema. Petri net based models for the specification and validation of protocols. In G. Rozenberg, H. Genrich, and G. Roucairol, editors, Advances in Petri Nets 1984, volume 188 of LNCS, pages 101–121. Springer-Verlag, Berlin, Germany, 1984. [DB78] P. J. Denning and J. P. Buzen. The operational analysis of queueing network models. ACM Computing Surveys, 10(3):225–261, September 1978. 240 BIBLIOGRAPHY [Deo74] N. Deo. Graph Theory with Applications to Engineering and Computer Science. Prentice-Hall, Englewood Cliffs, NJ, USA, 1974. [DLT90] Y. Dallery, Z. Liu, and D. Towsley. Equivalence, reversibility and symmetry properties in fork/join queueing networks with blocking. Technical report, MASI 9032, University Paris 6, 4 Place Jussieu, Paris, France, June 1990. [DMFDD89] M. Di Mascolo, M. Y. Frein, Y. Dallery, and R. David. Modeling of kanban systems using Petri nets. In K. Stecke and R. Suri, editors, Proceedings of the 3rd ORSA/TIMS Conference on Flexible Manufacturing Systems, pages 307–312. Elsevier Science Publishers B.V. (North Holland), 1989. [Erl09] A. K. Erlang. The theory of probabilities and telephone conversations. Nyt Tidsskrift Matematik, 20:33– 39, 1909. [ES83] D. L. Eager and K. C. Sevcik. Performance bound hierarchies for queueing networks. ACM Transactions on Computer Systems, 1(2):99–115, May 1983. [ES86] D. L. Eager and K. C. Sevcik. Bound hierarchies for multiple-class queueing networks. Journal of the ACM, 33(1):179–206, January 1986. [ES90] J. Esparza and M. Silva. On analysis and synthesis of free choice systems. Technical report, GISI-RR-90-10, Dpto. de Ingenier´ıa El´ectrica e Inform´atica, Universidad de Zaragoza, Spain, June 1990. [Esp90] J. Esparza. Structure Theory of Free Choice Nets. PhD thesis, Dpto. de Ingenier´ıa El´ectrica e Inform´atica, Universidad de Zaragoza, Zaragoza, Spain, June 1990. Research Report GISI-90-03. BIBLIOGRAPHY 241 [FN85a] G. Florin and S. Natkin. Les r´eseaux de Petri stochastiques. Technique et Science Informatiques, 4(1):143– 160, February 1985. In French. [FN85b] G. Florin and S. Natkin. Les r´eseaux de Petri stochastiques, 1985. Thesis de Doctorat d’Etat, Universit´e Pierre et Marie Curie, Paris (in French). [FN86] G. Florin and S. Natkin. One-place unbounded stochastic Petri nets: Ergodicity criteria and steady-state solutions. Journal of Systems and Software, 6(1,2):103–115, May 1986. [FN89a] G. Florin and S. Natkin. Matrix product form solution for closed synchronized queuing networks. In Proceedings of the 3rd International Workshop on Petri Nets and Performance Models, pages 29–37, Kyoto, Japan, December 1989. IEEE-CS Press. [FN89b] G. Florin and S. Natkin. Necessary and sufficient ergodicity condition for open synchronized queueing networks. IEEE Transactions on Software Engineering, 15(4):367– 380, April 1989. [GN67] W. J. Gordon and G. F. Newell. Closed queueing systems with exponential servers. Operations Research, 15:254–265, 1967. [GN72] R. S. Garfinkel and G. L. Nemhauser. Integer Programming. John Wiley & Sons, 1972. [GP87] E. Gelenbe and G. Pujolle. Introduction to Queuing Networks. John Wiley & Sons, 1987. [Hac72] M. H. T. Hack. Analysis of production schemata by Petri nets. M. S. Thesis , TR-94, M.I.T.,Boston, USA, 1972. 242 BIBLIOGRAPHY [Hil88] H. P. Hillion. Timed Petri nets and application to multistage production systems. In Proceedings of the 9th European Workshop on Applications and Theory of Petri Nets, pages 164–182, Venice, Italy, June 1988. [HL84] P. Heidelberger and S. S. Lavenberg. Computer performance evaluation methodology. IEEE Transactions on Computers, 33(12):1195–1220, December 1984. [HP89] H. P. Hillion and J. M. Proth. Performance evaluation of job-shop systems using timed event-graphs. IEEE Transactions on Automatic Control, 34(1):3–9, January 1989. [HT83] P. Heidelberger and K. S. Trivedi. Analytic queueing models for programs with internal concurrency. IEEE Transactions on Computers, 32:73–82, January 1983. [HV85] M. A. Holliday and M. K. Vernon. A generalized timed Petri net model for performance analysis. In Proceedings of the International Workshop on Timed Petri Nets, pages 181–190, Torino, Italy, July 1985. IEEE-CS Press. [IA89] S. M. R. Islam and H. H. Ammar. On bounds for token probabilities in a class of generalized stochastic Petri nets. In Proceedings of the 3rd International Workshop on Petri Nets and Performance Models, pages 221–227, Kyoto, Japan, December 1989. IEEE-CS Press. [Jac63] J. R. Jackson. Jobshop-like queueing systems. Management Science, 10(1):131–142, October 1963. [JLL77] N. Jones, L.H. Landweber, and Y. Lien. Complexity of some problems in Petri nets. Theoretical Computer Science, 4:277–299, 1977. [Kar84] N. Karmarkar. A new polynomial time algorithm for linear programming. Combinatorica, 4:373–395, 1984. BIBLIOGRAPHY 243 [KBB86] K. M. Kavi, B. P. Buckles, and U. N. Bhat. A formal definition of dataflow graph models. IEEE Transactions on Computers, 35(11):940–948, November 1986. [KBB87] K. M. Kavi, B. P. Buckles, and U. N. Bhat. Isomorphisms between Petri nets and dataflow graphs. IEEE Transactions on Software Engineering, 13(10):1127– 1134, October 1987. [Kel76a] T.W. Keller. Computer System Models with Passive Resources. PhD thesis, University of Texas at Austin, Austin, TX, USA, 1976. [Kel76b] F. P. Kelly. Networks of queues. Advances on Applied Probability, 8:416–432, 1976. [Kle75] L. Kleinrock. Queueing Systems Volume I: Theory. John Wiley & Sons, New York, NY, USA, 1975. [Kle76] L. Kleinrock. Queueing Systems Volume II: Computer Applications. John Wiley & Sons, New York, NY, USA, 1976. [Kri84] J. Kriz. Throughput bounds for closed queueing networks. Performance Evaluation, 4:1–10, 1984. [Lau87] K. Lautenbach. Linear algebraic calculation of deadlocks and traps. In K. Voss, H. Genrich, and G. Rozenberg, editors, Concurrency and Nets, pages 315–336. SpringerVerlag, Berlin, 1987. [Lav89] S. S. Lavenberg. A perspective on queueing models of computer performance. Performance Evaluation, 10:53– 76, 1989. [LB86] J.Y. Le Boudec. A BCMP extension to multiserver stations with concurrent classes of customers. In Proceedings of PERFORMANCE’86 and ACM SIGMETRICS, Raleigh, NC, USA, May 1986. 244 BIBLIOGRAPHY [Lit61] J. D. C. Little. A proof of the queueing formula L=λW. Operations Research, 9:383–387, 1961. [LR78] L. H. Landweber and E. L. Robertson. Properties of conflict-free and persistent Petri nets. Journal of the ACM, 25(3):352–364, April 1978. [LR87] A. A. Lazar and T. G. Robertazzi. Markovian Petri net protocols with product form solution. In Proceedings of the Conference on Computer Communications, pages 1054–1062, Washington, DC, USA, 1987. IEEECS Press. [LZGS84] E. D. Lazowska, J. Zahorjan, G. S. Graham, and K. C. Sevcik. Quantitative System Performance. PrenticeHall, Inc., Englewood Cliffs, NJ, USA, 1984. [Mag84] J. Magott. Performance evaluation of concurrent systems using Petri nets. Information Processing Letters, 18:7–13, 1984. [Mai87] D. Mailles. Files d’Attente Descriptives pour la Modelisation de la Synchronisation dans les Systemes Informatiques. PhD thesis, Laboratoire MASI, Univ. P. et M. Curie, Paris, France, September 1987. Technical Report 202 (in French). [MB86] M. Minoux and G. Bartnik. Graphes, Algorithmes, Logiciels. Dunod Informatique, Paris, France, 1986. [Mol81] M.K. Molloy. On the Integration of Delay and Throughput Measures in Distributed Processing Models. PhD thesis, UCLA, Los Angeles, CA, USA, 1981. [Mol82] M. K. Molloy. Performance analysis using stochastic Petri nets. IEEE Transaction on Computers, 31(9):913– 917, September 1982. [Mol85] M.K. Molloy. Fast bounds for stochastic Petri nets. In Proceedings of the International Workshop on Timed