% This file was created with JabRef 2.4.2. % Encoding: Cp1252 @ARTICLE{RC-TCST-19, author = {R.J. Rodr\'{i}guez and J. Campos}, title = {On Throughput Approximation of Resource-Allocation Systems by Bottleneck Regrowing}, journal = {IEEE Transactions on Control Systems Technology}, year = {2019}, volume = {27}, pages = {370-377}, number = {1}, month = {January}, abstract = {Complex systems, such as manufacturing, logistics, or Web services, are commonly modeled as discrete event systems dealing with the resource-allocation problem. In particular, Petri nets (PNs) are a widely used formalism to model these systems. Although their functional properties have been extensively studied in the literature, their nonfunctional properties (such as throughput) have usually been ignored. In this brief, we focus on a PN subclass useful for modeling concurrent sequential processes with shared resources, termed S4PR nets. For these nets, we present an iterative strategy that makes intensive use of mathematical programming problems to approximate system throughput. Initially, our strategy selects the slowest part (a subsystem) of the net. Then, the next slowest parts are considered. In each step, the throughput is computed solving analytically the underlying continuous-time Markov chain when feasible (or by simulation, otherwise). Since only certain subsystems are considered, the state-explosion problem inherent to the increasing net size is mitigated. We evaluate our strategy in a set of randomly generated S4PR nets. Our findings show that the throughput improves the upper throughput bound computation by almost 20% and that small portions of the net are enough to approximate system throughput.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/rc-tcst-19.pdf}, doi={10.1109/TCST.2017.2768512} } @INPROCEEDINGS{RC-JCSD18, author = {R.J. Rodr\'{i}guez and J. Campos}, title = {Extended Abstract: On Throughput Approximation of Resource-Allocation Systems by Bottleneck Regrowing}, booktitle = {Actas de las {XXV} Jornadas de Concurrencia y Sistemas Distribuidos}, year = {2018}, address = {Toledo, Spain}, month = {June}, publisher = {Universidad Complutense de Madrid y Universidad de Castilla-La Mancha}, abstract = {Complex systems, such as manufacturing, logistics, or Web services, are commonly modeled as discrete event systems dealing with the resource-allocation problem. In particular, Petri nets (PNs) are a widely used formalism to model these systems. Although their functional properties have been extensively studied in the literature, their nonfunctional properties (such as throughput) have usually been ignored. In this brief, we focus on a PN subclass useful for modeling concurrent sequential processes with shared resources, termed S4PR nets. For these nets, we present an iterative strategy that makes intensive use of mathematical programming problems to approximate system throughput. Initially, our strategy selects the slowest part (a subsystem) of the net. Then, the next slowest parts are considered. In each step, the throughput is computed solving analytically the underlying continuous-time Markov chain when feasible (or by simulation, otherwise). Since only certain subsystems are considered, the state-explosion problem inherent to the increasing net size is mitigated. We evaluate our strategy in a set of randomly generated S4PR nets. Our findings show that the throughput improves the upper throughput bound computation by almost 20% and that small portions of the net are enough to approximate system throughput.}, note = {See the paper \cite{RC-TCST-19}}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/rc-jcsd18.pdf}, doi={} } @INPROCEEDINGS{PCFD-ARGENCON-16, author = {S. P{\'e}rez and J. Campos and H. Facchini and A. Dantiacq}, title = {Experimental Study of Unicast and Multicast Video Traffic using {WAN} Test Bed}, booktitle = {Proceedings of the 2016 IEEE Biennial Congress of Argentina {(ARGENCON'16)}}, year = {2016}, pages = {1-6}, address = {Buenos Aires, Argentina}, month = {June}, publisher = {IEEE Computer Society}, abstract = {The deployment of IP multicast protocols in each router in the path is needed to access the benefits of the multicast. IP multicast exists today mainly in LAN networks and in small areas of highly controlled interconnected networks. In fact, some companies started to offer tailored solutions to try to overcome these limitations. On the other hand, over the last decade, the multimedia applications have expanded rapidly, and in particular in video applications. There are Internet sites that offer movies on-line; and it is common for users to upload and download videos with sites like YouTube (\copyright Google Inc.). The video call via the Internet is common with applications, such as Skype (\copyright Microsoft). The growth of video traffic should be taken into account when designing a network. Understanding the behavior of the video traffic and the requirements for the network helps network administrators to improve the traffic planning. In this work, a quantitative analysis is performed by experimentation, in order to evaluate the behavior and impact of video traffic on WAN networks. We propose a WAN test bed composed by a video traffic server and several client stations that allows injecting unicast and multicast video traffic, compressed with several codecs. From capturing video traffic, we identified several interesting unicast and multicast performance metrics, such as: throughput, number of frames, delays, jitter, and interframe spaces and frame sizes distributions. Several factors have been taken into account: the video resolution configuration, the type of video, and restrictions on the bandwidth, as in a corporate real WAN link of some few Mbps. This study facilitates the comparison of the results with those obtained from analytical and modelling studies for different contexts.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/pcfd-argencon-16.pdf}, doi={10.1109/ARGENCON.2016.7585260} } @INPROCEEDINGS{PFCTHM-CHILECON-15, author = {S. P{\'e}rez and H. Facchini and J. Campos and C. Taffernaberry and F. Hidalgo and S. M{\'e}ndez}, title = {Behavior of Codecs for Multicast Video Traffic using {WAN} Test Bed}, booktitle = {Proceedings of the 2015 Chilean Conference on Electrical, Electronics Engineering, Information and Communication Technologies {(CHILECON'15)}}, year = {2015}, pages = {269-274}, address = {Santiago, Chile}, month = {October}, publisher = {IEEE Computer Society}, abstract = {In recent years there has been an exponential increase in the growth in multimedia applications, and in particular in video applications. Understanding the behavior of the video traffic and the requirements for the network helps network administrators to improve the traffic. In this work, a quantitative analysis is performed by experimentation, in order to evaluate the behavior and impact of video traffic on WAN networks. We propose a WAN test bed composed by a video traffic server and several client stations. This article introduces a scenario that allows to inject multicast video traffic, compressed with several codecs. From capturing video traffic, we identified several interesting performance metrics, such as multicast throughput, interframe space and frame size distributions, and the number of frames. We include detailed contributions on the impact produced by several factors, such as the configuration of the resolution of the video, the video class, the codec used for the compression, and the use of multicast traffic when there are restrictions on the bandwidth, as in a corporate real WAN link of some few Mbps. This study facilitates the comparison of the results with those obtained from analytical studies and modelling for different contexts.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/pfcthm-chilecon-15.pdf}, doi={10.1109/Chilecon.2015.7400387} } @Book{QEST2015, Title = {Quantitative Evaluation of Systems}, Year = {2015}, Editor = {J. Campos and B. Haverkort}, Publisher = {Springer}, Series = {Lecture Notes in Computer Science}, Volume = {9259}, Note = {Proceedings of the 12th International Conference on Quantitative Evaluation of Systems (QEST 2015), Madrid, Spain, September 1-3, 2015}, url = {http://www.springer.com/us/book/9783319222639}, doi={10.1007/978-3-319-22264-6} } @ARTICLE{PFDCC-JCST-15, author = {S. P{\'e}rez and H. Facchini and A. Dantiacq and G. Cangemi and J. Campos}, title = {Analysis of Impact in the {Wi-Fi QoS} of the {EDCA} Parameters}, journal = {Journal of Computer Science \& Technology}, year = {2015}, volume = {15}, pages = {8-14}, number = {1}, month = {April}, abstract = {With the continuing development of the wireless technologies (Wi-Fi, 3G, 4G, WiMax and Bluethooth), the study of wireless multimedia transmissions has gained lately more attention. For example, the expectations of the company leaders on the growth of Wi-Fi video traffic has updated the lines of research on the standard IEEE 802.11e introduced to provide QoS (Quality of Service) to WLAN (Wireless LAN ) networks. In this paper we updated with greater accuracy, using other resources and the experience gained since the emergence of the standard, the work carried out previously on the quantitative impact of each EDCA (Enhanced Distributed Channel Access) parameter on the overall performance of the mechanisms MAC. A quantitative analysis of the optimizations that can be achieved has been performed by simulation. We use a node model EDCA 802.11e with the tool M{\"o}bius of the University of Illinois, which supports an extension of SPN (Stochastic Petri Networks), known as HSAN (Hierarchical Stochastic Activity Networks), what favors the contrast with other tools or mathematical resources. We use a realistic scenario formed by Wi-Fi stations with the capacity to transmit voice, video and best effort traffic. The results show that the default setting of EDCA parameters is not optimal, and that with an appropriate selection, very significant improvements can be obtained.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/pfdcc-jcst-15.pdf}, doi={} } @INPROCEEDINGS{PFDCC-CONIELECOMP-15, author = {S. P{\'e}rez and H. Facchini and A. Dantiacq and G. Cangemi and J. Campos}, title = {An Evaluation of {QoS} for intensive video traffic over 802.11e {WLANs}}, booktitle = {Proceedings of the 25th International Conference on Electronics, Communications and Computers {(CONIELECOMP'15)}}, year = {2015}, pages = {8-15}, address = {Puebla, Mexico}, month = {February}, publisher = {IEEE Computer Society}, abstract = {With the continuing development of the wireless technologies (Wi-Fi, 3G, 4G, WiMax and Bluethooth), the study of wireless multimedia transmissions has gained lately more attention. For example, the expectations of the company leaders on the growth of Wi-Fi video traffic has updated the lines of research on the standard IEEE 802.11e introduced to provide QoS (Quality of Service) to WLAN (Wireless LAN ) networks. A quantitative analysis has been performed by simulation. We use a node model EDCA (Enhanced Distributed Channel Access) 802.11e with the tool M{\"o}bius of the University of Illinois, which supports an extension of SPN (Stochastic Petri Networks), known as HSAN (Hierarchical Stochastic Activity Networks). This formalism favors the comparison of the results with those obtained from other tools, based mainly on simulation languages, for Wi-Fi stations with the capacity to transmit voice, video or best effort traffic in presence of error. This article introduces novel scenario that varies the load by increasing the number of active stations from 5 to 45 but maintaining their relative traffic proportion. The proportion of traffic injected by stations is 65\% video, 2\% voice, and 33\% best effort. Measured performance metrics were absolute or direct performance, relative performance, average delay of queue, and average queue size.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/pfdcc-conielecomp-15.pdf}, doi={10.1109/CONIELECOMP.2015.7086933} } @BOOK{CSX-FMM-Book-2014, title = {Formal Methods in Manufacturing}, publisher = {CRC Press}, year = {2014}, editor = {J. Campos and C. Seatzu and X. Xie}, abstract = {Design and operation of manufacturing systems and their supply chains is a domain of significant research worldwide. The complexity of this domain stems from the large dimension of such systems that are highly parallel and distributed, from significant sources of uncertainties and from the degrees of flexibility. Formal methods are mathematical techniques, often supported by tools, for developing man-made systems. Formal methods and mathematical rigor enable manufacturing engineers to handle fundamental design principles, such as abstraction or modular and hierarchical development, and to deal with typical engineering problems and quality goals, like reliability, flexibility, and maintainability. Formal methods can provide both a deep understanding of the system, thus helping to cover holes in the specification, and an improved system reliability, through verification and validation of the desired properties. Automata, statecharts, queueing networks, Petri nets, min-max algebras, process algebras, and temporal logic-based models are becoming more and more used for an integrated view of design specification, validation, performance evaluation, planning, scheduling and control of manufacturing systems and their supply chains. This book presents some of the most significant works representing the state of the art in the area of formal methodologies for manufacturing systems, combining fundamentals and advanced issues. It is divided into four main parts, each devoted to a specific issue: modelling and simulation, supervisory control (including deadlock prevention), performance evaluation (including scheduling and optimization), and fault diagnosis and reconfiguration. Several formalisms are considered, including finite state automata, Petri nets (discrete, timed, continuous, and hybrid), process algebra and max-plus algebra, exemplifying the advantages of each of them in the solution of a specific problem.Within each part, more detailed problems are considered, and themost significant solutions are discussed and illustratedwith a series of interesting and significant examples in themanufacturing area. Individual chapters are written by leading experts in the field. Each topic is illustrated in detail, its significance in manufacturing systems is underlined, and the most important contributions in that specific area are surveyed. The book is intended for researchers, postgraduate students and engineers interested in problems occurring in manufacturing systems. In particular, it provides a comprehensive overview of the most important formal model-based solutions to a series of major problems in manufacturing systems and their supply chains, which are based on formal and rigorous modelling of the underlying system. Each chapter in the book aims at providing a balance mixture of (1) fundamental theory, giving the reader a clear introduction to the most important formalisms used for the modelling, analysis and control of manufacturing systems; (2) tutorial value, providing the state of the art on a series of problems that occur in manufacturing systems, such as deadlock prevention, supervisory control, performance evaluation and fault diagnosis; and (3) applicability, presenting a series of case studies and applications taken from the industrial world, that make it particularly appealing to practitioners. A brief description of the book is as follows. Part I (Chapters 1 through 5) concerns modelling and simulation of manufacturing systems. Chapter 1 focuses on Petri nets (untimed and timed) and shows how these can be effectively used to represent manufacturing systems in a bottom-up and modular fashion. Chapter 2 deals with a particular class of manufacturing systems for which a linear representation in an algebraic structure called dioids can be given. Chapters 3 and 4 deal with hybrid models of manufacturing systems. In particular, Chapter 3 focuses on hybrid Petri nets (HPNs), a formalism that combines fluid and discrete event dynamics. Particular attention is devoted to first-order hybrid Petri nets (FOHPNs) whose continuous dynamics are piecewise constant. It is shown how FOHPNs can be effectively used to model both manufacturing systems and inventory control systems. Chapter 4 focuses on stochastic flow models (SFMs) that preserve the essential features needed to design effective controllers and potentially optimize performance without any need to estimate the corresponding optimal performance value with accuracy. An overview of recently developed general frameworks for infinitesimal perturbation analysis (IPA) is also presented, through which unbiased performance sensitivity estimates of typical manufacturing performance measures can be obtained in such SFMs with respect to various controllable parameters of interest. Finally, Chapter 5 deals with a problem occurring in many real manufacturing systems, namely, freight transportation. It reviews the established transportation system modelling, including theory and applications of transportation supply models, trip demand models and dynamic traffic assignment methods, both for passenger and freight transportation, and also points out the characteristics of freight transportation that influence the logistic chain performance. Part II (Chapters 6 through 12) is devoted to the supervisory control of manufacturing systems. In particular, Chapters 6 through 8 introduce deadlock avoidance/prevention policies; Chapters 9 through 12 deal with supervisory control problems. Chapter 6 addresses the problem of deadlock avoidance in flexibly automated manufacturing systems through the modelling abstraction of the (sequential) resource allocation system (RAS). The pursued analysis uses concepts and results from the formalmodelling framework of finite state automata (FSA). Chapter 7 investigates the problem of deadlock prevention in the Petri net framework. After an overview of the classical approaches based on the addition of monitors that prevent siphons to become empty, a novel methodology is presented. Chapter 8 also deals with Petri nets. Here the digraph theory is used to effectively derive control laws that avoid deadlocks in single unit RAS, that is, systems where each part requires a single unit of a single resource for each operation. In Chapter 9, Petri nets are used to solve supervisory control problems of manufacturing systems. Different problem statements, depending on the considered specifications, and different solutions are considered, in particular based on the theory of monitor places and on the theory of regions. Extended finite automata (EFA), that is, automata augmented with bounded discrete variables, and updates of these variables on the transitions, are introduced in Chapter 10 and effectively used to automatically synthesize a supervisor. Decentralized control and modular control problems are discussed in Chapter 11. Finally, Chapter 12 discusses how manufacturing systems can often be modeled as max-plus-linear (MPL) systems and controlled via model predictive control (MPC). Part III (Chapters 13 through 20) addresses the issue of performance evaluation of manufacturing systems and supply chains. Chapter 13 discusses approaches based on coloured Petri nets and state space analysis. Performance evaluation and control of manufacturing systems using fluid (i.e., continuous) Petri nets are discussed in Chapter 14. Chapter 15, discusses how timed process algebra called bounded true concurrency (BTC) can be effectively used for performance evaluation of flexible manufacturing systems. The problem of designing the lean, that is, the smallest buffers necessary and sufficient to achieve the desired line performance, is addressed in Chapter 16. Chapter 17 deals with the issue of inventory allocation and cycle time improvement in manufacturing systems and supply chains. Chapter 18 covers timed weighted event graphs, a subclass of Petri nets whose transitions are associated with workshops or specific treatments and whose places represent storages between the transitions. It deals with the minimization of the overall capacities of places, under throughput constraints. Chapter 19 focuses on the application of Petri nets to the scheduling of semiconductor manufacturing systems. To this aim, a hierarchical coloured timed Petri net (HCTPN) is proposed and genetic algorithms are extended and then embedded into the constructed HCTPN to find optimal/suboptimal schedules. Finally, Chapter 20 focuses on organization problems of health-care systems, presenting a Petri net-based software for health-care service modelling and simulation called MedPRO. Resource planning and scheduling are also in the scope of the tool. Finally, Part IV (Chapters 21 through 23) illustrates fault diagnosis approaches for discrete event systems that can be successfully applied to manufacturing systems. In particular, in Chapters 21 and 22 finite state automata and interpreted Petri nets, respectively, are used as reference formalisms. In both chapters, diagnosability analysis is also performed. Chapter 21 also discusses the problem of sensor selection for diagnosability and the problem of cooperative diagnosis for systems with decentralized information. Chapter 23 addresses a problem strictly related to fault diagnosis occurring in automated manufacturing systems, namely, that of online control reconfiguration.}, url = {http://www.crcpress.com/product/isbn/9781466561557}, doi={10.1201/b16529} } @ARTICLE{PCFB-LAT-13, author = {S. P{\'e}rez and J. Campos and H. Facchini and L. Bisaro}, title = {Tuning Mechanism for {IEEE 802.11e EDCA} Optimization}, journal = {IEEE Latin America Transactions}, year = {2013}, volume = {11}, pages = {1134-1142}, number = {4}, month = {June}, abstract = {The overall performance of a WLAN 802.11e is determined, among other things, by the Enhanced Distributed Channel Access (EDCA) parameters, typically configured with default and static values. The same does not vary according to the dynamic requirements of Quality of Service (QoS) of the network. To achieve significant improvements in the performance of the network, and simultaneously comply with the specifications of QoS, a new algorithm of tuning is proposed to make the adjustment of these parameters dynamically, which we call Algorithm for the Differentiation of Traffic Multiple (MTDA). The algorithm has been evaluated in realistic scenarios with noise, reaching a initialization effective, rapid convergence, and the differentiation of effective multiple wireless traffic (voice, video and best effort with Pareto distribution). It adopted a model of wireless station implemented in Hierarchical Stochastic Activities Networks (HSANs), which runs on the simulator M{\"o}bius.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/pcfb-lat-13.pdf}, doi={10.1109/TLA.2013.6601760} } @ARTICLE{BC-TSMC-13, author = {S. Bernardi and J. Campos}, title = {A min-max problem for the computation of the cycle time lower bound in interval-based {Time} {Petri} {Nets}}, journal = {IEEE Transactions on Systems, Man, and Cybernetics: Systems}, year = {2013}, volume = {43}, pages = {1167-1181}, number = {5}, month = {September}, abstract = {The Time Petri Net with firing frequency intervals (TPNF) is a modeling formalism used to specify system behavior under timing and frequency constraints. Efficient techniques exist to evaluate the performance of TPNF models based on the computation of bounds of performance metrics (e.g., transition throughput, place marking). In this paper, we propose a min-max problem to compute the cycle time of a transition under optimistic assumptions. That is, we are interested in computing the lower bound. We will demonstrate that such a problem is related to a maximization linear programming problem (LP-max) previously stated in the literature, to compute the throughput upper bound of the transition. The main advantage of the min-max problem compared to the LP-max is that, besides the optimal value, the optimal solutions provide useful feedback to the analyst on the system behavior (e.g., performance bottlenecks). We have implemented two solution algorithms, using CPLEX APIs, to solve the min-max problem, and have compared their performance using a benchmark of TPNF models, several of these being case studies. Finally, we have applied the min-max technique for the vulnerability analysis of a critical infrastructure, i.e., the Saudi Arabian crude-oil distribution network.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/bc-tsmc-13.pdf}, doi = {10.1109/TSMCA.2012.2226442} } @INPROCEEDINGS{BC-JCSD13, author = {S. Bernardi and J. Campos}, title = {A min-max problem for the computation of the cycle time lower bound in interval-based {Time} {Petri} {Nets}}, booktitle = {Actas de las {XXI} Jornadas de Concurrencia y Sistemas Distribuidos}, year = {2013}, address = {San Sebasti{\'a}n, Spain}, month = {June}, publisher = {Universidad del Pa\'{\i}s Vasco}, abstract = {The Time Petri Net with firing frequency intervals (TPNF) is a modeling formalism used to specify system behavior under timing and frequency constraints. Efficient techniques exist to evaluate the performance of TPNF models based on the computation of bounds of performance metrics (e.g., transition throughput, place marking). In this paper, we propose a min-max problem to compute the cycle time of a transition under optimistic assumptions. That is, we are interested in computing the lower bound. We will demonstrate that such a problem is related to a maximization linear programming problem (LP-max) previously stated in the literature, to compute the throughput upper bound of the transition. The main advantage of the min-max problem compared to the LP-max is that, besides the optimal value, the optimal solutions provide useful feedback to the analyst on the system behavior (e.g., performance bottlenecks). We have implemented two solution algorithms, using CPLEX APIs, to solve the min-max problem, and have compared their performance using a benchmark of TPNF models, several of these being case studies. Finally, we have applied the min-max technique for the vulnerability analysis of a critical infrastructure, i.e., the Saudi Arabian crude-oil distribution network.}, note = {See the paper \cite{BC-TSMC-13}}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/bc-jcsd13.pdf}, doi={} } @ARTICLE{PFMBC-JCST-13, author = {S. P{\'e}rez and H. Facchini and G. Mercado and L. Bisaro and J. Campos}, title = {Throughput Quantitative Analysis of {EDCA} 802.11e in Different Scenarios}, journal = {Journal of Computer Science \& Technology}, year = {2013}, volume = {13}, pages = {16-23}, number = {1}, month = {April}, abstract = {This document presents a quantitative analysis of the direct and relative throughput of IEEE 802.11e. The global throughput of an 802.11e WLAN is determined by EDCA (Enhanced Distributed Channel Access) parameters, among other aspects, that are usually configured with predetermined and static values. This study carefully evaluates the Quality of Service (QoS) of Wi-Fi with EDCA in several realistic scenarios with noise and a blend of wireless traffic (e.g., voice, video, and best effort, with Pareto distribution). The metrics of the benefits obtained in each case are compared, and the differentiated impact of network dynamics on each case is quantified. The results obtained show that the default settings are not optimal, and that with an appropriate selection, can be achieved improvements of the order of 25%, according to the type of traffic. In addition, it could be shown the quantitative impact of each parameter EDCA on the overall performance. This study proposes a new experimental scenario based on the relative proportion of traffic present in the network. Stations have been simulated using the M{\"o}bius tool, which supports an extension of SPN (Stochastic Petri Networks), known as HSAN (Hierarchical Stochastic Activity Networks).}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/pfmbc-jcst-13.pdf}, doi={} } @INPROCEEDINGS{PFMBC-AINA-13, author = {S. P{\'e}rez and H. Facchini and G. Mercado and L. Bisaro and J. Campos}, title = {{EDCA} 802.11e performance under different scenarios. Quantitative analysis}, booktitle = {Proceedings of the 27th International Conference on Advanced Information Networking and Applications {(AINA'13)}}, year = {2013}, pages = {802-807}, address = {Barcelona, Spain}, month = {March}, publisher = {IEEE Computer Society}, abstract = {The global throughput of an 802.11e WLAN is determined by EDCA (Enhanced Distributed Channel Access) parameters, among other aspects, that are usually configured with predetermined and static values. This study carefully evaluates the Quality of Service (QoS) of Wi-Fi with EDCA in several realistic scenarios with noise and a blend of wireless traffic (e.g., voice, video, and best effort, with Pareto distribution). The metrics of the benefits obtained in each case are compared, and the differentiated impact of network dynamics on each case is quantified. This study proposes a new experimental scenario based on the relative proportion of traffic present in the network. Stations have been implemented using HSANs (Hierarchical Stochastic Activity Networks) and simulated using the M\"obius tool.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/pfmbc-aina-13.pdf}, doi={10.1109/AINA.2013.20} } @ARTICLE{BCM-TII-11, author = {S. Bernardi and J. Campos and J. Merseguer}, title = {Timing-failure risk assessment of {UML} design using {Time} {Petri} {Net} bound techniques}, journal = {IEEE Transactions on Industrial Informatics}, year = {2011}, volume = {7}, pages = {90-104}, number = {1}, month = {February}, abstract = {Software systems that do not meet their timing constraints can cause risks. In this work we propose a comprehensive method for assessing the risk of timing failure by evaluating the software design. We show how to apply best practises in software engineering and well-known Time Petri Net (TPN) modeling and analysis techniques, and we demonstrate the effectiveness of the method with reference to a case study in the domain of realtime embedded systems. The method customizes the Australian standard risk management process, where the system context is the UML-based software specification, enriched with standard MARTE profile annotations to capture non-functional system properties. During the risk analysis, a TPN is derived, via model transformation, from the software design specification and TPN bound techniques are applied to estimate the probability of timing failure. TPN bound techniques are also exploited, within the risk evaluation and treatment steps, to identify the risk causes in the software design.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/bcm-tii-11.pdf}, doi = {10.1109/TII.2010.2098415} } @ARTICLE{Cam-TII-10, author = {J. Campos}, title = {Guest Editorial: {Special Section on Formal Methods in Manufacturing}}, journal = {IEEE Transactions on Industrial Informatics}, year = {2010}, volume = {6}, pages = {125-126}, number = {2}, month = {May}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/cam-tii-10.pdf}, doi={10.1109/TII.2010.2042529} } @Book{ETFA-09, title = {Proceedings of the 14th IEEE International Conference on Emerging Technologies and Factory Automation}, year = {2009}, editor = {Antoni Grau and Javier Campos and Gabriel Oliver}, address = {Palma de Mallorca, Spain}, publisher = {IEEE Industrial Electronics Society}, month = {September}, url = {http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5340902}, doi={} } @ARTICLE{BC-TII-09, author = {S. Bernardi and J. Campos}, title = {Computation of Performance Bounds for Real-Time Systems Using Time {Petri} Nets}, journal = {IEEE Transactions on Industrial Informatics}, year = {2009}, volume = {5}, pages = {168-180}, number = {2}, month = {May}, abstract = {Time Petri Nets (TPNs) have been widely used for the verification and validation of real-time systems during the software development process. Their quantitative analysis consists in applying enumerative techniques that suffer the well known state space explosion problem. To overcome this problem several methods have been proposed in the literature, that either provide rules to obtain equivalent nets with a reduced state space or avoid the construction of the whole state space. In this paper, we propose a method that consists in computing performance bounds to predict the average operational behavior of TPNs by exploiting their structural properties and by applying operational laws. Performance bound computation was first proposed for Timed (Timed PNs) and Stochastic Petri nets (SPNs). We generalize the results obtained for Timed PNs and SPNs to make the technique applicable to TPNs and their extended stochastic versions: TPN with firing frequency intervals (TPNFs) and Extended TPNs (XTPNs). Finally, we apply the proposed bounding techniques on the case study of a robot-control application taken from the literature.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/bc-tii-09.pdf}, doi = {10.1109/TII.2009.2017201} } @ARTICLE{PJCS-TSMC-07, author = {C.J. P{\'e}rez-Jim{\'e}nez and J. Campos and M. Silva}, title = {Approximate Throughput Computation of Stochastic Weighted {T}-Systems}, journal = {IEEE Transactions on Systems, Man, and Cybernetics. Part A: Systems and Humans}, year = {2007}, volume = {37}, pages = {431-444}, number = {3}, month = {May}, abstract = {A general iterative technique for approximate throughput computation of stochastic live and bounded weighted T-systems is presented. It generalizes a previous technique on stochastic marked graphs. The approach has two basic foundations. First, a deep understanding of the qualitative behaviour of weighted T-systems leads to a general decomposition technique. Second, after the decomposition phase, an iterative response time approximation method is applied for the throughput computation. Existence of convergence points for the iterative approximation method can be proved. Experimental results generally have an error of less than 5%. The state space is usually reduced by more than one order of magnitude; therefore, the analysis of otherwise intractable systems is possible.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/pjcs-tsmc-07.pdf}, doi={10.1109/TSMCA.2007.893455} } @ARTICLE{CM-LNCS-06, author = {J. Campos and J. Merseguer}, title = {On the integration of {UML} and {Petri} nets in software development}, journal = {Lecture Notes in Computer Science}, year = {2006}, volume = {4024}, pages = {19-36}, note = {Invited paper}, abstract = {Software performance engineering deals with the consideration of quantitative analysis of the behaviour of software systems from the early development phases in the life cycle. This paper summarizes in a semiformal and illustrative way our proposal for a suitable software performance engineering process. We try to integrate in a very pragmatic approach the usual object oriented methodology ---supported with UML language and widespread CASE tools--- with a performance modelling formalism, namely stochastic Petri nets. A simple case study is used to describe the whole process. More technical details should be looked up in the cited bibliography.}, booktitle = {Petri Nets and Other Models of Concurrency - ICATPN 2006: 27th International Conference on Applications and Theory of Petri Nets and Other Models of Concurrency, Turku, Finland, June 26-30, 2006}, editor = {S. Donatelli and P. S. Thiagarajan}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/cm-lncs-06.pdf}, doi={10.1007/11767589_2} } @UNPUBLISHED{BCDM-05, author = {S. Bernardi and J. Campos and S. Donatelli and J. Merseguer}, title = {{GSPN} Compositional Semantics for {UML} Statecharts and Sequence Diagrams}, note = {Submitted for publication}, year = {2005}, abstract = {Software performance engineering (SPE) is proposed as a method for the performance evaluation of software systems early in the development process. The generic approach of the SPE consists of deriving performance models from UML specifications. This paper, following the SPE principles, addresses the UML StateCharts (SCs) and the Sequence Diagrams (SDs) as UML specifications, while performance models are specified with Generalized Stochastic Petri Nets. The proposed derivation, actually the authors interpretation of the SC and SD, provides these two kinds of UML diagrams with a formal semantics. The interpretation is based on the UML semi-formal semantics. A software fault tolerance mechanism is used as an example to illustrate how, following the proposal, the SC and the SD are automatically converted into GSPNs. Another contribution of the work is the consistency study among the SC and the SD, since they are used in a combined manner to obtain the target performance model. The approach presented in this paper allows to derive two kinds of performance models: one representing the behaviour of the whole system and another representing the particular execution described by a SD.} } @UNPUBLISHED{PJCS-05, author = {C.J. P{\'e}rez-Jim{\'e}nez and J. Campos and M. Silva}, title = {Approximate Throughput Computation of Deterministic Systems of Sequential Processes: Application to Manufacturing Systems}, note = {Submitted for publication}, year = {2005}, abstract = {A general iterative technique for approximate throughput computation of stochastic live and bounded Deterministic Systems of Sequential Processes (DSSPs, a subclass of Petri nets) is presented. It generalizes a previous technique on stochastic weighted T-systems. The approach has two basic foundations. First, a deep understanding of the qualitative behaviour of DSSPs leads to a general decomposition technique. Second, after the decomposition phase, an iterative response time approximation method is applied for the throughput computation. We apply the obtained technique to the performance evaluation of manufacturing systems modelled with Petri nets. Experimental results generally have an error of less than 5 %. The state space is usually reduced by more than one order of magnitude; therefore, the analysis of otherwise intractable systems is possible.} } @ARTICLE{MC-LNCS-04, author = {J. Merseguer and J. Campos}, title = {Software Performance Modelling Using {UML} and {Petri} Nets}, journal = {Lecture Notes in Computer Science}, year = {2004}, volume = {2965}, pages = {265-289}, note = {Invited paper}, abstract = {Software systems are today one of the most complex artifacts, they are simultaneously used by hundred-thousand of people sometimes in risk real time operations, such as auctions or electronic commerce. Nevertheless, it is a common practice to deploy them without the expected performance. Software Performance Engineering has emerged as a discipline to complement Software Engineering research in order to address this kind of problems. In this work, we survey some recent contributions in the field of Software Performance Engineering. The approach surveyed has as main features that it uses the UML diagrams to specify the functional and performance requeriments of the system and the stochastic Petri nets formalism to analyse it.}, booktitle = {Performance Tools and Applications to Networked Systems, Revised Tutorial Lectures from {MASCOTS} 2003}, editor = {M.C. Calzarossa and E. Gelenbe}, publisher = {Springer-Verlag}, series = {Tutorials}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/mc-lncs-04.pdf}, doi={10.1007/978-3-540-24663-3_13} } @INPROCEEDINGS{BC-QEST-04, author = {S. Bernardi and J. Campos}, title = {On Performance Bounds for Interval Time {Petri} Nets}, booktitle = {Proceedings of the 1st International Conference on Quantitative Evaluation of Systems {(QEST'04)}}, year = {2004}, pages = {50-59}, address = {Enschede, The Netherlands}, month = {September}, publisher = {IEEE Computer Society}, abstract = {Interval time Petri Nets are Petri nets in which time intervals are associated to transitions. Their quantitative analysis basically consists in applying enumerative techniques that suffer the well known state space explosion problem. To overcome this problem several methods have been proposed in the literature, that either allow to obtain equivalent nets with a reduced state space or avoid the construction of the whole state space. The alternative method proposed here consists in computing performance bounds to partially characterize the quantitative behavior of interval time Petri Nets by exploiting their structural properties and/or by applying operational laws. The performance bound computation is not a new technique: it has been proposed for timed Petri nets. In this paper we present the results obtained from a preliminary investigation on the applicability of bounding techniques of timed Petri nets to interval time Petri Nets.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/bc-qest-04.pdf}, doi = {10.1109/QEST.2004.1348019} } @INPROCEEDINGS{GBC-IROS-04, author = {C. Gonz{\'a}lez-Buesa and J. Campos}, title = {Solving the Mobile Robot Localization Problem Using String Matching Algorithms}, booktitle = {Proceedings of the 2004 {IEEE/RSJ} International Conference on Intelligent Robots and Systems {(IROS'04)}}, year = {2004}, pages = {2475-2480}, address = {Sendai, Japan}, month = {September}, abstract = {In this paper we address the mobile robot localization using some techniques borrowed from the Computational Biology community. The specific problem studied here is also known as the kidnapped robot problem. Our proposal is to solve this problem by string matching algorithms, which have experienced a large advance in the last years due to (for example) the Genoma Project. The paper uses three different algorithms to solve the mentioned problem and shows their advantages, such as the robustness of the results and the memory and time efficiency. These results are validated by real experimentation using panoramic images of indoor buildings, and compared and discussed with existing techniques that have been used over the same test-bed.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/gbc-iros-04.pdf}, doi={10.1109/IROS.2004.1389780} } @INPROCEEDINGS{LGMC-WOSP04, author = {J.P. L{\'o}pez-Grao and J. Merseguer and J. Campos}, title = {From {UML} Activity Diagrams to Stochastic {Petri} Nets: Application to Software Performance Engineering}, booktitle = {Proceedings of the Fourth International Workshop on Software and Performance {(WOSP'04)}}, year = {2004}, pages = {25-36}, address = {Redwood City, California, USA}, month = {January}, publisher = {ACM}, note = {Also in ACM SIGSOFT Software Engineering Notes, Vol. 29, no. 1, January 2004.}, abstract = {Over the last decade, the relevance of performance evaluation in the early stages of the software development life-cycle has been steadily rising. We honestly believe that the integration of formal models in the software engineering process is a must, in order to enable the application of well-known, powerful analysis techniques to software models. In previous papers the authors have stated a proposal for SPE, dealing with several UML diagram types.The proposal formalizes their semantics, and provides a method to translate them into (analyzable) GSPN models. This paper focuses on activity diagrams, which had not been dealt with so far. They will be incorporated in our SPE method, enhancing its expressivity by refining abstraction levels in the statechart diagrams. Performance requirements will be annotated according to the UML profile for schedulability, performance and time. Last but not least, our CASE tool prototype will be introduced. This tool deals with every model element from activity diagrams and ensures an automatic translation from ADs into GSPNs strictly following the process related in this paper.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/lgmc-wosp04.pdf}, doi={10.1145/974044.974048} } @ARTICLE{MCM-WINET03, author = {J. Merseguer and J. Campos and E. Mena}, title = {Analysing Internet Software Retrieval Systems: Modeling and Performance Comparison}, journal = {Wireless Networks: The Journal of Mobile Communication, Computation and Information}, year = {2003}, volume = {9}, pages = {223-238}, number = {3}, month = {May}, abstract = {Nowadays, there exist web sites that allow users to retrieve and install software in an easy way. The performance of these sites may be poor if they are used in wireless networks; the reason is the inadequate use of the net resources that they need. If this kind of systems are designed using mobile agent technology the previous problem might be avoided. In this paper, we present a comparison between the performance of a software retrieval system especially designed to be used in a wireless network and the performance of a software retrieval system similar to the well-known Tucows.com web site. In order to compare performance, we make use of a software performance process enriched with formal techniques. The process has as important features that it uses UML as a design notation and it uses stochastic Petri nets as formal model. Petri nets provide a formal semantics for the system and a performance model.}, publisher = {Kluwer Academic Publishers}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/mcm-winet03.pdf}, doi={10.1023/A:1022825210932} } @INPROCEEDINGS{MC-SERP03, author = {J. Merseguer and J. Campos}, title = {Exploring Roles for the {UML} Diagrams in Software Performance Engineering}, booktitle = {Proceedings of the 2003 International Conference on Software Engineering Research and Practice {(SERP'03)}}, year = {2003}, pages = {43-47}, address = {Las Vegas, Nevada, USA}, month = {June}, publisher = {CSREA Press}, abstract = {It is not an overstatement to say that the gap between software design and performance evaluation techniques has caused the misuse of the last ones by software engineers. The UML profile for schedulability, performance and time arose from the intention to close both fields, software engineering and performance analysis. Nevertheless the gap remains, since it is difficult for software engineers to devise which parts of their designs are suitable to represent performance requirements. The profile has started to study this problem from a scenarios viewpoint. In this work, we explore other viewpoints to deal with performance requirements at software design level.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/mc-serp03.pdf}, doi={} } @INPROCEEDINGS{MCM-SCI03, author = {J. Merseguer and J. Campos and E. Mena}, title = {A Pattern-Based Approach to Model Software Performance Using {UML} and {Petri} Nets: Application to Agent-Based Systems}, booktitle = {Proceedings of the 7th World Multiconference on Systemics, Cybernetics and Informatics}, year = {2003}, volume = {IX}, pages = {307-313}, address = {Orlando, Florida, USA}, month = {July}, publisher = {IIIS Press}, abstract = {Software design and implementation using mobile agents are nowadays involved in a scepticism halo. There are researchers who question its utility because it could be a new technology that does provide new skills but it could introduce new problems. Security and performance are the most critical aspects for this new kind of software. In this paper we present a formal approach to analyse performance for this class of systems, which is integrated in the early stages of the software development process. We propose to model the software system in a pragmatic way using as a design technique the well-known design patterns; from these models, the corresponding formal performance model, in terms of Petri nets, is obtained semi-automatically by applying a set of translation rules. Therefore, the formal performance model is obtained as a by-product of the software life-cycle, preserving the benefits of the software design techniques. Finally, the formal performance model is analysed, using analytical techniques, in order to study the performance of the system. Moreover, another benefit of the proposal is that it is possible to predict the behaviour of the system without the necessity of implementing it. To illustrate the proposal, we apply it to a software retrieval service system designed using mobile agents.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/mcm-sci03.pdf}, doi={} } @INPROCEEDINGS{GUGC-SEIO03, author = {A. Gonz{\'a}lez-Uz{\'a}bal and C. Gal{\'e} and J. Campos}, title = {Desarrollo de una herramienta de optimizaci\'on binivel utilizando {CPLEX} y {MATLAB} y generaci\'on de problemas de prueba}, booktitle = {Actas del 27 Congreso Nacional de Estad\'{\i}stica e Investigaci\'on Operativa}, year = {2003}, pages = {2931-2944}, address = {Lleida, Spain}, month = {April}, organization = {Sociedad de Estad\'{\i}stica e Investigaci\'on Operativa de Espa\~na y Departament de Matem\`atica de la Universidad de Lleida}, publisher = {Edicions de la Universitat de Lleida}, note = {In Spanish}, abstract = {En este trabajo se presenta el desarrollo de una herramienta para resolver problemas de optimizaci\'on binivel y en particular de un nivel, tanto con objetivos lineales como lineales fraccionarios, implementada en CPLEX y en MATLAB. La herramienta permite seleccionar entre varios algoritmos de resoluci\'on y obtener medidas de evaluaci\'on del rendimiento de cada uno. Se presenta tambi\'en un m\'etodo para la generaci\'on autom\'atica de problemas binivel de prueba que ayude a evaluar este tipo de herramientas. Mediante una serie de transformaciones de la matriz de coeficientes tecnol\'ogicos y la funci\'on objetivo de segundo nivel, se asegura la factibilidad del problema y que la soluci\'on del problema binivel no sea la trivial.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/gugc-seio03.pdf}, doi={} } @INPROCEEDINGS{LGMC-02c, author = {J.P. L{\'o}pez-Grao and J. Merseguer and J. Campos}, title = {Performance Engineering Based on {UML} and {SPNs}: A Software Performance Tool}, booktitle = {Proceedings of the Seventeenth International Symposium on Computer and Information Sciences}, year = {2002}, pages = {405-409}, address = {Orlando, Florida, USA}, month = {October}, organization = {University of Central Florida}, publisher = {CRC Press}, abstract = {The increasing relevance of UML as a semi-formal modelling paradigm has entailed the need for an adjustment of the classical performance evaluation methods within the scope of the new working environment. Under these circumstances, a formal semantics for the UML language and a strong mathematical substratum are required in order to be able to compute performance estimates and validate logical properties in the first stages of the software life-cycle. We believe that stochastic Petri nets are specially suited for this aim. A compositional approach for the translation of several UML diagrams into analyzable Petri net models has there fore been considered in previous papers. Following this ap proach, we will focus here in the depiction of a model case study from the perspective of our new performance-oriented CASE tool.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/lgmc-02c.pdf}, doi={} } @INPROCEEDINGS{MBCD-wodes02, author = {J. Merseguer and S. Bernardi and J. Campos and S. Donatelli}, title = {A Compositional Semantics for {UML} State Machines Aimed at Performance Evaluation}, booktitle = {Proceedings of the 6th International Workshop on Discrete Event Systems}, year = {2002}, editor = {M. Silva and A. Giua and J.M. Colom}, pages = {295-302}, address = {Zaragoza, Spain}, month = {October}, publisher = {IEEE Computer Society Press}, abstract = {Unified Modeling Language (UML) is gaining widespread acceptance as an effective way to describe the behaviour of systems. As such it has also attracted the attention of researchers that are interested in deriving, automatically, performance evaluation models from system's descriptions. A required step to automatically produce a performance model (as any executable model) is that the semantics of the description language is formally defined. Among the various models of UML we concentrate on States Machines and we build a semantics for them in terms of Generalized Stochastic Petri Nets, a well established modelling formalism for the performance evaluation of distributed systems. The paper introduces rules that allow to derive from a description of a system, expressed as a set of State Machines, an executable GSPN model. The semantics is compositional since the executable GSPN model is obtained by composing, using standard Petri Net operators, the GSPN models of the single State Machines, and each GSPN model is obtained by composition of submodels for State Machine basic features such as internal and outgoing transitions, states, actions, and events.}, institution = {Departamento de Inform\'atica e Ingenier\'{\i}a de Sistemas, Universidad de Zaragoza}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/mbcd-wodes02.pdf}, doi={10.1109/WODES.2002.1167702} } @INPROCEEDINGS{LGMC-02b, author = {J.P. L{\'o}pez-Grao and J. Merseguer and J. Campos}, title = {On the Use of Formal Models in Software Performance Evaluation}, booktitle = {Actas de las {X} Jornadas de Concurrencia}, year = {2002}, pages = {367-387}, address = {Jaca, Spain}, month = {June}, publisher = {Universidad de Zaragoza}, abstract = {Importance of performance evaluation at first stages of the software development life-cycle has been progressively rising. We believe that the need for integration of formal models in the software engineering process is a must in order to apply well-known analysis techniques to software models. In previous papers it has been stated our proposal of extension of UML semantics for some diagram types and a complete method to translate them into GSPN models. Here we will focus on activity diagrams: a new translation method for them will be presented, while we explain their link with other UML diagrams such as statecharts so as to amplify the expressivity at system description. Last but not least, our CASE tool prototype will be introduced. As it will be seen, every modeling aspect for these diagrams will be covered and, thanks to it, the translation process will be automatically performed.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/lgmc-02b.pdf} } @Book{JC-02, title = {Actas de las {X} Jornadas de Concurrencia}, year = {2002}, editor = {J. Campos and J. Ezpeleta and J. J{\'u}lvez and J. Merseguer and C.J. P{\'e}rez-Jim{\'e}nez and F. Tricas}, address = {Zaragoza}, publisher = {Ed. Kronos. ISBN 84-88502-98-2}, month = {June}, url = {http://webdiis.unizar.es/jjcc02/} } @UNPUBLISHED{CCCMMPPRS-02, author = {J. Campos and J. Casanovas and J.M. Colom and G. Mart\'{i}n and J. Mart\'{i}nez and A. Pont and R. Puigjaner and A. Robles and M.R. Sancho}, title = {Informe sobre la adaptaci\'on de los estudios de {TIC} a la {D}eclaraci\'on de {B}olonia}, note = {In Spanish}, address = {Barcelona, Spain}, year = {2002}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/cccmmpprs-02.pdf} } @ARTICLE{MCM-LNCS-01, author = {J. Merseguer and J. Campos and E. Mena}, title = {A Performance Engineering Case Study: Software Retrieval System}, journal = {Lecture Notes in Computer Science}, year = {2001}, volume = {2047}, pages = {317-332}, abstract = {This chapter presents a case study in performance engineering. The case study consists of a Software Retrieval System based on agents. The system is modelled in a pragmatic way using the Unified Modeling Language and in a formal way using stochastic Petri Nets. Once the system has been modelled, performance figures are obtained from the formal model. Finally, some concluding remarks are obtained from our experience in the software performance process.}, address = {Heidelberg}, booktitle = {Performance Engineering. State of the Art and Current Trends}, editor = {R. Dumke and C. Rautenstrauch and A. Schmietendorf and A. Scholz}, publisher = {Springer-Verlag}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/mcm-lncs-01.pdf}, doi={10.1007/3-540-45156-0_20} } @INPROCEEDINGS{MCM-JJCC-01, author = {J. Merseguer and J. Campos and E. Mena}, title = {Web-Based Versus Mobile Agent-Based Software Retrieval Systems: Performance Comparison}, booktitle = {Actas de las {IX} Jornadas de Concurrencia}, year = {2001}, pages = {299-312}, address = {Sitges, Spain}, month = {June}, publisher = {Universitat Ramon Llull}, abstract = {Nowadays, there exist web sites that allow users to retrieve and install software in an easy way. The performance of these sites may be poor if they are used in wireless networks; the reason is the inadequate use of the net resources they need. If this kind of systems are designed using mobile agent technology the previous problem might be avoided. In this paper, we present a comparison between the performance of a software retrieval system especially designed to be used in wireless networks (e.g., mobile computers) and the performance of a software retrieval system similar to the well-known Tucows.com or Download.com web sites. In order to compare performance, we make use of a software performance process enriched with formal techniques. The process has as important features that it uses UML as a design notation and it uses stochastic Petri nets as formal model. Petri nets provide a formal semantics for the system and a performance model.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/mcm-jjcc-01.pdf} } @INPROCEEDINGS{Cam-EVI-01, author = {J. Campos}, title = {Evaluaci\'on de Prestaciones de Sistemas Concurrentes Modelados con Redes de {Petri}}, booktitle = {Actas de la {XI} Escuela de Verano de Inform\'atica de la Universidad de Castilla-La Mancha}, year = {2001}, pages = {141-156}, address = {Universidad de Castilla-La Mancha, Albacete, Spain}, month = {July}, publisher = {Departamento de Inform\'atica}, note = {In Spanish}, abstract = {Formal methods are the most suitable way to model and analyze several kinds of software systems. However, conventional methods are gaining placed in Software Engineering field because they can be easily applied in all the stages of the software life cycle. The combination of formal and conventional methods could be an interesting approach to describe and analyze some software aspects, as for example, the performance of the system. In this way, we make use of a software performance process enriched with formal techniques. The process has as important features that it uses UML as a design notation and it uses stochastic Petri nets as formal model. Petri nets provide a formal semantics for the system and a performance model, while UML supplies the framework and tools to document the system. The process is used in this article to present a performance comparison between software retrieval systems. Nowadays, there exist web sites that allow users to retrieve and install software in an easy way. The performance of these sites may be poor if they are used in wireless networks; the reason is the inadequate use of the net resources they need. In this article, we show that if this kind of systems are designed using mobile agent technology the previous problem might be avoided.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/cam-evi-01.pdf} } @INPROCEEDINGS{MCM-MSWiM-01, author = {J. Merseguer and J. Campos and E. Mena}, title = {Performance Analysis of Internet Based Software Retrieval Systems Using {Petri} Nets}, booktitle = {Proceedings of the 4th {ACM} International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems, within the 7th International Conference on Mobile Computing and Networking}, year = {2001}, editor = {M. Meo and T. Dahlberg and L. Donatiello}, pages = {47-56}, address = {Rome, Italy}, month = {July}, publisher = {ACM}, abstract = {Nowadays, there exist web sites that allow users the retrieval and installation of software in an easy way. The performance of this task may be poor because of an inadequate use of the net resources. If these kind of systems were designed using mobile agent technology this problem might be avoided. In this paper, we present a comparison between the performance of a software retrieval system designed using mobile agents and the performance of a software retrieval system similar to the well-known Tucows or Download.com web sites. In order to compare performance, we make use of a software performance process enriched with formal techniques. The process has as important features that it uses UML as a design notation and it uses Petri nets as formal model. Petri nets provide a formal semantic for the system and a performance model.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/mcm-mswim-01.pdf}, doi={10.1145/381591.381604} } @INPROCEEDINGS{MCM-WOSP-00, author = {J. Merseguer and J. Campos and E. Mena}, title = {A Pattern-Based Approach to Model Software Performance}, booktitle = {Proceedings of the Second International Workshop on Software and Performance}, year = {2000}, pages = {137-142}, address = {Ottawa, Canada}, month = {September}, publisher = {ACM}, abstract = {The use of the object-oriented paradigm in the software industry is nowadays a reality. Approximations like frameworks, components, workflows or patterns are gaining place, sometimes to complement object-oriented development. Like the object-oriented paradigm of these approaches make special emphasis on the reuse of the software as a way to increase productivity. But the performance of software systems is not as good as desired. Thus, techniques to predict it are subject of research. Software Performance Engineering is concerned with these problems. Here we present an approach to reuse performance models developed in the early stages of the software development process. The approach has as a goal the use of formal models to predict performance.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/mcm-wosp-00.pdf}, doi={10.1145/350391.350421} } @INPROCEEDINGS{MCM-JJCC-00, author = {J. Merseguer and J. Campos and E. Mena}, title = {Evaluating Performance on Mobile Agents Software Design}, booktitle = {Actas de las VIII Jornadas de Concurrencia}, year = {2000}, editor = {D. Cazorla}, pages = {291-307}, address = {Cuenca, Spain}, month = {June}, publisher = {Universidad de Castilla-la Mancha}, abstract = {Software design and implementation using mobile agents are nowadays involved in a scepticism halo. There exist researchers who question its utility because it could be a new technology which no new skills but could introduce new problems. Security and performance are the most critical aspects for this new kind of software. In this contribution we present a formal approach to analyze performance for this class of systems. Our approach is integrated in the early stages of the software development process. In this way, it is possible to predict expected behaviour without the necessity of carry out the complete implementation phase. To show the approach, we model a software retrieval service system in a pragmatic way, after the corresponding formal model is obtained and analyzed in order to study performance.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/mcm-jjcc-00.pdf} } @INPROCEEDINGS{MCM-SEPN-00, author = {J. Merseguer and J. Campos and E. Mena}, title = {Performance Evaluation for the Design of Agent-Based Systems: A {Petri} Net Approach}, booktitle = {Proceedings of the Workshop on Software Engineering and Petri Nets, within the 21st International Conference on Application and Theory of Petri Nets}, year = {2000}, editor = {Mauro Pezz{\'e} and Sol M. Shatz}, pages = {1-20}, address = {Aarhus, Denmark}, month = {June}, publisher = {University of Aarhus}, abstract = {Software design and implementation using mobile agents are nowadays involved in a scepticism halo. There exist researchers who question its utility because it is a new technology that could provide no new skills but it could introduce new problems. Security and performance are the most critical aspects for this new kind of software. In this contribution we present a formal approach to analyze performance for this class of systems. Our approach is integrated in the early stages of the software development process. In this way, it is possible to predict expected behaviour without the necessity to carry out the complete implementation phase. To show the approach, we model a software retrieval service system in a pragmatic way, after the corresponding formal model is obtained and analyzed in order to study performance.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/mcm-sepn-00.pdf}, doi={} } @TECHREPORT{C-RR-00-00, author = {J. Campos}, title = {{Petri} Nets}, institution = {Departamento de Inform\'atica e Ingenier\'{\i}a de Sistemas}, year = {2000}, type = {Internal Report}, address = {Universidad de Zaragoza}, month = {February}, abstract = {A brief introduction (3 pages) to the topic for an Encyclopedia.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/c-rr-00-00.pdf} } @INPROCEEDINGS{C-Zaragoza-99, author = {J. Campos}, title = {{PNPM'99-PAPM'99-NSMC'99 Tutorial}: Properties and Bounds on {P/T} Nets}, booktitle = {Tutorials of the 8th International Workshop on Petri Nets and Performance Models, 7th International Workshop on Process Algebra and Performance Modelling, and 3rd International Meeting on Numerical Solution of Markov Chains}, year = {1999}, address = {Zaragoza, Spain}, month = {September}, abstract = {A complementary approach to exact or approximation techniques for the analysis of timed or stochastic Petri net models is the computation of bounds for their performance measures. 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. In this tutorial, net-driven techniques for the computation of bounds for the main performance indices of timed Petri net models are considered. Special attention is given tothe intimate relationship between qualitative and quantitative aspects of Petri nets. In particular, the intensive use of structure theory of net models allows to obtain very efficient computation techniques.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/c-zaragoza-99.pdf} } @INPROCEEDINGS{PJC-PNPM99, author = {C.J. P{\'e}rez-Jim{\'e}nez and J. Campos}, title = {On State Space Decomposition for the Numerical Analysis of Stochastic {Petri} Nets}, booktitle = {Proceedings of the 8th International Workshop on Petri Nets and Performance Models}, year = {1999}, pages = {32-41}, address = {Zaragoza, Spain}, month = {September}, publisher = {IEEE Computer Society Press}, abstract = {Net-driven decomposition techniques are considered in this paper in order to reduce the state explosion problem for the computation of performance indices of stochastic Petri nets. Basically, the idea is to represent (or partially represent) in a decomposed manner the reachability graph of the model so it can be used for exact and/or approximated performance analysis. In that way, the complete storing of the graph is avoided and, for the case of approximate analysis, the solution of the isomorphous continuous time Markov chain is substituted by the solution of smaller components. The techniques are applied to a couple of non-trivial models.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/pjc-pnpm99.pdf}, doi={10.1109/PNPM.1999.796530} } @ARTICLE{CDS-TSE-99, author = {J. Campos and S. Donatelli and M. Silva}, title = {Structured Solution of Asynchronously Communicating Stochastic Modules}, journal = {IEEE Transactions on Software Engineering}, year = {1999}, volume = {25}, pages = {147-165}, number = {2}, month = {March}, abstract = {Asynchronously Communicating Stochastic Modules (SAM) are Petri nets that can be seen as a set of modules that communicate through buffers, so they are not (yet another) Petri net subclass, but they complement a net with a structured view. This paper considers the problem of exploiting the compositionality of the view to generate the state space and to find the steady-state probabilities of a stochastic extension of SAM in a net-driven, efficient way. Essentially, we give an expression of an auxiliary matrix, G, which is a supermatrix of the infinitesimal generator of a SAM. G is a tensor algebra [Davio 1981] expression of matrices of the size of the components for which it is possible to numerically solve the characteristic steady-state solution equation pi.G = 0, without the need to explicitly compute G. Therefore, we obtain a method that computes the steady-state solution of a SAM without ever explicitly computing and storing its infinitesimal generator, and therefore without computing and storing the reachability graph of the system. Some examples of application of the technique are presented and compared to previous approaches.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/cds-tse-99.pdf}, doi={10.1109/32.761442} } @INPROCEEDINGS{PJC-JJCC99, author = {C. J. P{\'e}rez-Jim{\'e}nez and J. Campos}, title = {On State Space Decomposition for the Numerical Analysis of Stochastic {Petri} Nets}, booktitle = {Actas de las VII Jornadas de Concurrencia}, year = {1999}, editor = {J.M. Bernab{\'e}u and F.D. Mu{\~n}oz}, pages = {249-268}, address = {Gand{\'{\i}}a, Spain}, month = {June}, publisher = {Universidad Polit{\'e}cnica de Valencia}, abstract = {Stochastic Petri nets is a well-known formalism adequate for the design, validation, and performance evaluation of discrete event systems, computer systems, manufacturing systems, telecommunication networks, and so on. In this paper, we deal with three different techniques to decompose the state space of a general stochastic Petri net that can be used to decrease the time and memory requirements of numerical analysis algorithms. The presented techniques are based on the divide and conquer principle to compute from the original model several submodels. These submodels can be used for a functional analysis, structural analysis and performance evaluation (exact and approximate). In this paper we apply the techniques to approximate throughput computation.} } @INCOLLECTION{C-MATCH17-98, author = {J. Campos}, title = {Performance Bounds}, booktitle = {Performance Models for Discrete Event Systems with Synchronizations: Formalisms and Analysis Techniques}, publisher = {Editorial KRONOS}, year = {1998}, editor = {G. Balbo and M. Silva}, chapter = {17}, pages = {587-635}, address = {Zaragoza, Spain}, month = {September}, abstract = {A complementary approach to exact or approximation techniques for the analysis of queueing network models is the computation of bounds for their performance measures. 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. In this chapter, we concentrate in net-driven techniques for the computation of bounds for the main performance indices of timed Petri net models. Previous works on bounds computation for classical queueing networks are not included here and the interested reader is referred to the bibliographic remarks in Section 17.5. The presented techniques are characterized by their interest in stressing the intimate relationship between qualitative and quantitative aspects of Petri nets. In particular, the intensive use of structure theory of net models allows to obtain very efficient computation techniques. The organization of the chapter is the following. In Section 17.1, a general approach for the computation of upper and lower bounds for arbitrary linear functions of average marking of places and throughput of transitions of both timed Place/Transition nets and timed Well-Formed Coloured nets is presented. Section 17.2 includes a more intuitive approach for the computation of throughput upper bounds, even if it is valid only for restricted Petri net subclasses. The relation of this technique with the general approach and the attainability of the bound for a particular subclass of nets is included. In Section 17.3, two possible improvements of upper and lower throughput bounds are presented using implicit places and liveness bounds of transitions, respectively. All the bounds computed in Sections 17.1, 17.2 and 17.3 are insensitive to the timing probability distributions since they are based only on the knowledge of the average service times. Section 17.4 includes a brief overview of three additional techniques for the improvement of the bounds. Since some additional assumptions on the form of the probability distribution functions associated to the service of transitions or on the conflict resolution policies are done, the obtained bounds are non-insensitive. Finally, some bibliographic remarks are included in Section 17.5.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/c-match17-98.pdf} } @INCOLLECTION{C-MATCH23-98, author = {J. Campos}, title = {Response Time Approximation for Stochastic Marked Graphs}, booktitle = {Performance Models for Discrete Event Systems with Synchronizations: Formalisms and Analysis Techniques}, publisher = {Editorial KRONOS}, year = {1998}, editor = {G. Balbo and M. Silva}, chapter = {23}, pages = {797-817}, address = {Zaragoza, Spain}, month = {September}, abstract = {A general iterative technique for approximate throughput computation of strongly connected stochastic marked graphs (SMG's) is presented in this Chapter. We consider SMG's with time and marking independent exponentially distributed service times associated with transitions. The approach has two basic foundations. First, it is deeply based on qualitative theory of MG's. More precisely, given an arbitrary cut (subset of places producing a net partition), a structural decomposition technique is developed that allows us to split a strongly connected MG into two aggregated subsystems and a basic skeleton system. And what is more important, the behaviours of the subsystems, including steps, language of firing sequences and reachable markings, are equivalent to the whole system behaviour (projected on the corresponding subsets of nodes). Second, after the decomposition phase, an iterative response time approximation method is applied for the computation of the throughput. Experimental results on several examples generally have an error of less than 3%. The state space is usually reduced by more than one order of magnitude; therefore the analysis of otherwise intractable systems is possible. The Chapter is organized as follows. In Section 23.1, some fundamental properties on MG's and implicit places are presented. Section 23.2 includes the structural decomposition of MG's used in the rest of the Chapter. The iterative technique for approximate throughput computation is described in Section 23.3. Section 23.4 includes several application examples to illustrate the introduced technique. Finally, some bibliographic remarks are included in Section 23.5.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/c-match23-98.pdf} } @INCOLLECTION{C-MATCH8-98, author = {J. Campos}, title = {Performance Measures and Basic Properties}, booktitle = {Performance Models for Discrete Event Systems with Synchronizations: Formalisms and Analysis Techniques}, publisher = {Editorial KRONOS}, year = {1998}, editor = {G. Balbo and M. Silva}, chapter = {8}, pages = {285-304}, address = {Zaragoza, Spain}, month = {September}, abstract = {A goal of performance modelling with timed Petri nets (TPN's) is the estimation of some quantifiable performance measures of the system under consideration by the simulation or analysis of the model of the system behaviour. In order to do that, responsiveness and utilization performance measures of the system must be described in terms of average values of operational quantities defined on the TPN model, like the average marking of a place or the firing frequency of a transition. In Section 8.1, the usual average performance indices for TPN models are derived operationally from the basic observable events that were defined in Chapter 3. Sections 8.2 and 8.3 are devoted to exploit the operational approach for the definition of performance measures. In Section 8.2, operational analysis techniques are used to partially characterize the behaviour of TPN models. Classical operational laws, like Little's law are stated in Petri net terms. Additionally, some operational inequalities are derived that are typical of the presence of synchronization and that have not been considered before in the framework of queueing networks models. Section 8.3 illustrates another aspect of the deep gap, from the analytical point of view, existing between classical monoclass product-form queueing networks and TPN's. While in Gordon-Newell networks the vector of visit ratios to the stations can be easily (efficiently) computed from the routing information, in the case of bounded TPN's the computability of such index is a quite complex problem. This problem leads to a classification of net models attending to the dependency of the visit ratios on the net structure and the probabilistic routing, on the initial marking, and on the firing time of transitions. Since few operational analysis techniques can presently be used to compute the performance indices of interest, the classical approach based on stochastic processes must be considered. Section 8.4 introduces also the definition of performance parameters on the TPN model as expected values of the random variables that characterize the behaviour of the model, under some stochastic assumptions. As the reader surely knows, under ergodicity conditions the average (operationally defined) performance indices are equal to the expected (stochastically defined) indices, thus the techniques that will be presented later on for the computation of expected values will be useful to compute the average performance measures of interest. Some bibliographic remarks are summarized in Section 8.5.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/c-match8-98.pdf} } @INCOLLECTION{SC-MATCH20-98, author = {M. Silva and J. Campos}, title = {Introduction to Net-Driven Decomposition Techniques}, booktitle = {Performance Models for Discrete Event Systems with Synchronizations: Formalisms and Analysis Techniques}, publisher = {Editorial KRONOS}, year = {1998}, editor = {G. Balbo and M. Silva}, chapter = {20}, pages = {693-718}, address = {Zaragoza, Spain}, month = {September}, abstract = {As stated in previous chapters, a fundamental question in the use of stochastic Petri net models for performance evaluation, even under Markovian stochastic interpretation, is the so called state explosion problem. A general approach to deal with (computational) complexity is to use a divide and conquer strategy, what requires the definition of a decomposition method and the subsequent composition of partial results to get the full solution. On the other hand, the trade-off between computational cost and accuracy of the solution leads to the use of approximation or bounding techniques (for instance, throughput bounds can be computed in polynomial time on the number of transitions and places, see Chapter 17). In this context, a pragmatic compromise to be handled by the analyzer of a system concerns the definition of faithful models, that may be very complex to exactly analyse (what may lead to the use of approximation or just bounding techniques), or simplified models, for which exact analysis can be, eventually, accomplished. Divide and conquer strategies can be used with exact, approximate, or bounding techniques. The techniques for performance evaluation present in the literature consider either implicit or explicit decomposition of net models. In [7] (see Chapter 17), an implicit decomposition into P-semiflows is used for computing throughput bounds for arbitrary pdf of time durations. In [19] (see Chapter 12), a decomposition into disjoint modules (usually subnets generated by P-semiflows) is defined by the analyzer or provided by model construction; the computational technique uses directly the information provided by the modules to compute exact global limit probability distribution vector. In [8], a decomposition into modules (connected through buffers) should also be provided. In this case, the modules are complemented with an abstract view of their environment in the full model, and the approximate solution is computed through an iterative technique looking for a fixed point (details will be presented in Chapter 23). In the sequel of this Chapter and in a general context, components will refer to (eventually) complemented modules. They are just the elements used to build the full solution. In order to get efficient techniques, the decomposition and, eventually, complementation process should be net-driven (i.e., derived at net level). For this, we shall use PN's structure theory concepts and techniques (e.g., P-semiflows, implicit places, etc.). The Chapter is organised as follows. The main ideas behind net-driven decompositions of PN's are introduced in Section 20.1: the conservative and consistent components (Section 20.1.1), an example of implicit search technique into conservative components (Section 20.1.2), an explicit decomposition of nets, designating the modules to be used (Section 20.1.3), and the complementation of modules to get components (that include information from the environment), using implicit places (Section 20.1.4). A taxonomy for net-driven decomposition techniques is proposed in Section 20.2, providing a framework for the consideration of a significant number of performance evaluation methods. Several representative examples of techniques present in the literature are briefly overviewed and classified according with the classification criteria. Some concluding remarks are included in Section 20.3.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/sc-match20-98.pdf} } @INPROCEEDINGS{SC-wodes98, author = {M. Silva and J. Campos}, title = {Performance Evaluation of {DEDS} with Conflicts and Synchronizations: Net-Driven Decomposition Techniques}, booktitle = {Proceedings of the 4th International Workshop on Discrete Event Systems}, year = {1998}, pages = {398-413}, address = {Cagliari, Italy}, month = {August}, publisher = {IEE Control}, abstract = {A fundamental question in performance evaluation, even under Markovian interpretation, is the so called state explosion problem, what arises if no closed solution exists (e.g., a product-form). In order to deal with computationally complex problems, divide and conquer strategies are sometimes successful. Here we focus on the applicability of net structure theory to the decomposition phase. A taxonomy using two criteria allows to situate many performance evaluation techniques in the literature. The solution or composition phase may employ techniques as different as Kronecker algebra, response time approximation or bottleneck analysis.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/sc-wodes98.pdf}, doi={} } @INPROCEEDINGS{PJC-98, author = {C.J. P{\'e}rez-Jim{\'e}nez and J. Campos}, title = {A Response Time Approximation Technique for Stochastic General {P/T} Systems}, booktitle = {Proceedings of the 2nd IMACS International Multiconference on Computational Engineering in Systems Applications (CESA'98)}, year = {1998}, address = {Hammamet, Tunisia}, month = {April}, abstract = {Stochastic Petri nets is a well-known formalism adequate for the design, validation, and performance evaluation of discrete event and manufacturing systems. In this paper, we deal with steady-state throughput approximation of complex concurrent systems modelled with stochastic Petri nets. More precisely, we generalize to arbitrary stochastic P/T systems a response time approximation technique that was firstly proposed for special net subclasses. The presented technique is based on the divide and conquer principle and it is achieved in two steps. The first one, a net-driven decomposition of the model into several subsystems and the second one, an iterative solution algorithm that computes a throughput approximation of the original model transitions based on the solution of the embedded continuous time Markov chain of the subsystems. Experimental results on several examples generally have an error of less than 5%, and the state space is usually reduced by more than one order of magnitude.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/pjc-98.pdf}, doi={} } @INPROCEEDINGS{BC-StMalo-97, author = {B. Baynat and J. Campos}, title = {{PNPM'97 Tutorial}: Approximate Methods Based on Net-Driven Decompositions}, booktitle = {Tutorials of the 7th International Workshop on Petri Nets and Performance Models}, year = {1997}, address = {Saint Malo, France}, month = {June}, abstract = {A major drawback for the practical use of stochastic Petri net models lies in the state explosion problem originated when the exact solution of the associated continuous time Markov chain is achieved. This tutorial presents some ideas an examples on approximation techniques that try to overcome the state explosion problem within a divide and conquer strategy and with a strong exploitation of structural (qualitative) knowledge of the underlying Petri net model for both the decomposition and the solution phases.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/bc-stmalo-97.pdf} } @INPROCEEDINGS{CDS-StMalo-97, author = {J. Campos and S. Donatelli and M. Silva}, title = {Structured Solution of Stochastic {DSSP} Systems}, booktitle = {Proceedings of the 7th International Workshop on Petri Nets and Performance Models}, year = {1997}, pages = {91-100}, address = {Saint Malo, France}, month = {June}, publisher = {IEEE Computer Society Press}, abstract = {Deterministically Synchronized Sequential Processes (DSSP) are essentially states machines that communicate, may be in complex forms but under some restricted patterns, through buffer places; their definition is compositional by nature. This paper considers the problem of exploiting this compositionality to generate the state space and to find the steady state probabilities of a stochastic extension of DSSP in a net-driven, efficient way. Essentially, we give an expresion of an auxiliary matrix, G, which is a supermatrix of the infinitesimal generator of a DSSP. G is a tensor algebra expression of matrices of the size of the components for which it is possible to numerically solve the characteristic equation pi.G = 0, without the need to explicitly compute G. Therefore, we obtain a method that computes the steady state solution of a DSSP without ever explicitly computing and storing its infinitesimal generator, and therefore without computing and storing the reachability graph of the system.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/cds-stmalo-97.pdf}, doi={10.1109/PNPM.1997.595540} } @INPROCEEDINGS{PJCS-96b, author = {C.J. P{\'e}rez-Jim{\'e}nez and J. Campos and M. Silva}, title = {Approximate Throughput Computation of a Class of Cooperating Sequential Processes}, booktitle = {Proceedings of the Rensselaer's Fifth International Conference on Computer Integrated Manufacturing and Automation Technology (CIMAT'96)}, year = {1996}, pages = {382-389}, address = {Grenoble, France}, month = {May}, abstract = {We concentrate on a family of Discrete Event Dynamic Systems (DEDS), modelled with Petri nets and obtained from a simple modular design principle, that include in a controlled way primitives to deal with concurrency, decisions, synchronization, blocking, and bulk movements of jobs. Many assembly systems with complex behaviours at the machine level can be described with the class of DEDS under study. We present a structure based decomposition technique and use a fixed-point search iterative process based on response time preservation of subsystems to approximate the throughput. An extensive battery of numerical experiments has shown that the error is less than 3%, and that the state space is usually reduced by more than one order of magnitude.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/pjcs-96b.pdf}, doi={} } @INPROCEEDINGS{PJCS-96c, author = {C.J. P{\'e}rez-Jim{\'e}nez and J. Campos and M. Silva}, title = {On Approximate Performance Evaluation of Manufacturing Systems Modelled with Weighted {T}-Systems}, booktitle = {Proceedings of the IMACS/IEEE-SMC Multiconference on Computational Engineering in Systems Applications (CESA'96)}, year = {1996}, pages = {201-207}, address = {Lille, France}, month = {July}, abstract = {Approximate throughput computation of a class of discrete event systems (DES) modelled with stochastic weighted T-systems is considered. Stochastic weighted T-systems are the weighted extension of well known stochastic marked graphs Petri net subclass and are usually presented as a useful model to deal with bulk consumptions or productions of resources in manufacturing systems working on a cyclic basis. The iterative response time approximation technique that we present is deeply based on a previous structural decomposition and aggregation of the net model. Experimental results on several examples generally have and error of less than 5%. The state space is usually reduced by more than one order of magnitude; therefore, the analysis of otherwise intractable systems is possible.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/pjcs-96c.pdf}, doi={} } @INPROCEEDINGS{PJCS-96a, author = {C.J. P{\'e}rez-Jim{\'e}nez and J. Campos and M. Silva}, title = {State Machine Reduction for the Approximate Performance Evaluation of Manufacturing Systems Modelled with Cooperating Sequential Processes}, booktitle = {Proceedings of the 1996 IEEE International Conference on Robotics and Automation}, year = {1996}, pages = {1159-1165}, address = {Minneapolis, Minnesota, USA}, month = {April}, abstract = {We concentrate on a family of discrete event systems obtained from a simple modular design principle that include in a controlled way primitives to deal with concurrency, decisions, synchronization, blocking, and bulk movements of jobs. Due to the functional complexity of such systems, reliable throughput approximation algorithms must be deeply supported on a structure based decomposition technique. We present a decomposition technique and a fixed-point search iterative process based on response time preservation of subsystems. An extensive battery of numerical experiments has shown that the error is less than 3%, and that the state space is usually reduced by more than one order of magnitude.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/pjcs-96a.pdf}, doi={10.1109/ROBOT.1996.506864} } @BOOK{EDA-book-95, title = {Estructuras de Datos y Algoritmos}, publisher = {Prensas Universitarias de Zaragoza}, year = {1995}, author = {J. Campos}, series = {Colecci{\'o}n Textos Docentes}, address = {Pedro Cerbuna, 12, Zaragoza, Spain}, note = {In Spanish}, abstract = {La abstracci\'on de acciones es la base de la metodolog\'{\i}a de dise\~no descendente por refinamientos sucesivos, \'util para la resoluci\'on de peque\~nos problemas de tratamiento de informaci\'on. Sin embargo, para afrontar la construcci\'on de programas en media y gran escala es necesaria una metodolog\'{\i}a de dise\~no modular, que permita la partici\'on del trabajo en unidades de programa que puedan ser desarrolladas independientemente del resto. El prop\'osito de estos apuntes es presentar los principios b\'asicos de una metodolog\'{\i}a de dise\~no modular basada en la abstracci\'on de datos. Este material ha sido elaborado para servir como soporte de la asignatura Estructuras de datos y algoritmos, que se imparte en el tercer semestre de los estudios de Ingenier\'{\i}a Inform\'atica en el Centro Polit\'ecnico Superior de la Universidad de Zaragoza. Los alumnos que cursan dicha asignatura han seguido previamente dos semestres de programaci\'on en los que han debido aprender a especificar formalmente y dise\~nar programas en peque\~na escala, utilizando tipos de datos sencillos (como los predefinidos en un lenguaje de programaci\'on de la familia del Pascal); los alumnos conocen t\'ecnicas de dise\~no recursivo e iterativo, as\'{\i} como las herramientas b\'asicas para poder medir la eficiencia de los algoritmos (atendiendo a su tiempo de ejecuci\'on). No obstante, el material presentado puede ser \'util tambi\'en para un segundo nivel en todos aquellos planes de estudios en los que se incluyan dos cursos de programaci\'on de computadores. Pueden encontrarse en las librer\'{\i}as varios trabajos (muchos de ellos ya cl\'asicos) con t\'{\i}tulos similares o iguales a \'este. Sin embargo, y \'esta es la raz\'on para la existencia de uno nuevo, la aproximaci\'on al tema que se pretende desarrollar es bien diferente. De hecho, el t\'{\i}tulo que el autor habr\'{\i}a elegido, en caso de no haber optado por mantener el nombre de la asignatura antes mencionada, hubiese sido m\'as bien "Tipos abstractos de datos y algoritmos" o mejor "Introducci\'on a la programaci\'on con tipos abstractos de datos". La diferencia estriba en el \'enfasis que se pretende dar en las p\'aginas que siguen a la especificaci\'on formal de los tipos (de ah\'{\i} el t\'ermino "tipos abstractos de datos") como herramienta fundamental para el dise\~no modular de programas, en lugar de limitarse a presentar las estructuras de datos necesarias para representar los valores de los tipos definidos. El comentario anterior no debe hacer pensar al lector que el material que sigue es original del autor. Nada m\'as lejos de la realidad. \'Unicamente nos hemos limitado a enlazar las excelentes aproximaciones existentes en la literatura a la definici\'on y conceptos relacionados con los tipos abstractos de datos y su especificaci\'on algebraica (v\'eanse, por ejemplo, los dos \'ultimos cap\'{\i}tulos de la obra de Ricardo Pe\~na titulada Dise\~no de Programas. Formalismo y Abstracci\'on) con los trabajos m\'as cl\'asicos sobre estructuras de datos y algoritmos de manipulaci\'on (como, por ejemplo, Estructuras de Datos y Algoritmos, de Aho, Hopcroft y Ullman). Los apuntes est\'an estructurados en lecciones, agrupadas en grandes temas. En el primero de ellos, titulado "Tipos abstractos de datos", se presentan los conceptos fundamentales sobre los tipos abstractos de datos, su especificaci\'on formal (algebraica) y su utilizaci\'on en el dise\~no modular de programas. El segundo tema, "Tipos de datos lineales", introduce tres de los tipos abstractos lineales m\'as representativos y \'utiles en programaci\'on: las pilas, las colas y las listas con acceso por posici\'on. Para cada nuevo tipo presentado se incluyen su especificaci\'on formal, una o varias soluciones para la representaci\'on de sus valores, la implementaci\'on de las operaciones m\'as importantes, su coste computacional y algunos ejemplos de aplicaci\'on. El tercer tema, titulado "\'Arboles y esquemas algor\'{\i}tmicos", incluye los detalles sobre algunos de los tipos de \'arboles m\'as frecuentemente utilizados, como los \'arboles binarios, \'arboles ordenados, \'arboles de b\'usqueda, mont\'{\i}culos, ..., y ejemplos de aplicaci\'on. Adem\'as se introducen los algoritmos de vuelta atr\'as y las heur\'{\i}sticas voraces. Los dos \'ultimos temas, sobre "Tipos de datos funcionales" (o tablas) e "Introducci\'on a los grafos", no se desarrollan con la misma extensi\'on que los anteriores por razones diferentes. En el caso de las tablas, tras las definiciones formales convenientes, se hace hincapi\'e en la representaci\'on mediante tablas dispersas basadas en la utilizaci\'on de una funci\'on de localizaci\'on (hashing, en ingl\'es) y en las tablas multidimensionales representadas mediante estructuras de listas m\'ultiples, pues otras representaciones posibles basadas en listas lineales o \'arboles de b\'usqueda no precisan mayor explicaci\'on tras el estudio de los temas previos. En cuanto a los grafos, los alumnos de Ingenier\'{\i}a Inform\'atica (a quienes va dirigida preferentemente esta obra) han cursado previamente una asignatura titulada "Matem\'atica discreta", en la que se les ha presentado el concepto de grafo y una buena colecci\'on de algoritmos para su manipulaci\'on. Por ello, y atendiendo a razones de completitud, se presentan s\'olo las especificaciones formales y varias alternativas de representaci\'on, junto a algunas consideraciones sobre el efecto que la elecci\'on de la representaci\'on tiene en el coste de los algoritmos de manipulaci\'on. Por \'ultimo, un comentario sobre las notaciones empleadas y los lenguajes de programaci\'on que pueden servir como soporte de pr\'acticas. Para la especificaci\'on algebraica de tipos abstractos, se utiliza una sintaxis similar a la del lenguaje OBJ, pero en espa\~nol. En cuanto a los m\'odulos, estructuras de datos y algoritmos, se emplea una notaci\'on algor\'{\i}tmica, tambi\'en en espa\~nol, que consiste en una extensi\'on modular de la notaci\'on utilizada en los apuntes sobre Introducci\'on a la programaci\'on, elaborados por Javier Mart\'{\i}nez y Javier Campos como soporte a la asignatura de igual nombre existente en el curriculum de Ingenier\'{\i}a Inform\'atica del CPS. En cuanto al lenguaje de programaci\'on soporte de las pr\'acticas, el autor desaconseja la utilizaci\'on de las extensiones modulares de Pascal (incluido el Modula 2), pues carecen de la posibilidad de definir tipos opacos y tipos gen\'ericos, siendo ambos mecanismos fundamentales en la metodolog\'{\i}a desarrollada. As\'{\i}, un lenguaje apropiado resulta ser el Ada, dotado de la posibilidad de definici\'on de tipos opacos y tipos gen\'ericos, con una sintaxis y sem\'antica bien pensadas y una dificultad de aprendizaje similar al Pascal, si se limita su presentaci\'on a la parte secuencial. Otras alternativas pueden encontrarse en lenguajes de programaci\'on orientados a objetos (como, por ejemplo, C++), dada la cercan\'{\i}a de los conceptos de "clase" y "tipo abstracto de dato".}, url = {http://puz.unizar.es/catalogo/detalle.php?l=467}, doi={} } @INCOLLECTION{CCHS-QMIPSbook-95, author = {J. Campos and J.M. Colom and H. Jungnitz and M. Silva}, title = {Approximate Throughput Computation of Stochastic Marked Graphs}, booktitle = {Quantitative Methods in Parallel Systems}, publisher = {Springer}, year = {1995}, editor = {F. Baccelli and A. Jean-Marie and I. Mitrani}, series = {Esprit Basic Research Series}, pages = {175-188}, abstract = {A general iterative technique for approximate throughput computation of stochastic strongly connected marked graphs is presented. It generalizes a previous technique based on net decomposition through a single input-single output cut, allowing the split of the model through any cut. The approach has two basic foundations. First, a deep understanding of the qualitative behaviour of marked graphs leads to a general decomposition technique. Second, after the decomposition phase, an iterative response time approximation method is applied for the computation of the throughput. Experimental results on several examples generally have an error of less than 3%. The state space is usually reduced by more than one order of magnitude; therefore the analysis of otherwise intractable systems is possible.}, doi={10.1007/978-3-642-79917-4_12} } @INCOLLECTION{CACCM-QMIPSbook-95, author = {G. Chiola and C. Anglano and J. Campos and J.M. Colom and M. Silva}, title = {Operational Analysis of Timed {Petri} Nets and Application to the Computation of Performance Bounds}, booktitle = {Quantitative Methods in Parallel Systems}, publisher = {Springer}, year = {1995}, editor = {F. Baccelli and A. Jean-Marie and I. Mitrani}, series = {Esprit Basic Research Series}, pages = {161-174}, abstract = {We use operational analysis techniques to partially characterize the behaviour of timed Petri nets under very weak assumptions on their timing semantics. New operational inequalities are derived that are typical of the presence of synchronization and that were therefore not considered in queueing network models. We show an interesting application of the operational laws to the statement and the efficient solution of problems related to the estimation of performance bounds insensitive to the timing probability distributions. The results obtained generalize and improve in a clear setting results that were derived in the last few years for several different subclasses of timed Petri nets. In particular the extension to Well-Formed Coloured nets appears straightforward and allows an efficient exploitation of models symmetries.}, doi={10.1007/978-3-642-79917-4_11} } @INCOLLECTION{TSCC-QMIPSbook-95, author = {E. Teruel and M. Silva and J.M. Colom and J. Campos}, title = {Functional and Performance Analysis of Cooperating Sequential Processes}, booktitle = {Quantitative Methods in Parallel Systems}, publisher = {Springer}, year = {1995}, editor = {F. Baccelli and A. Jean-Marie and I. Mitrani}, series = {Esprit Basic Research Series}, pages = {52-65}, abstract = {This paper presents some results concerning the functional and performance analysis of sequential proceses connected through buffers using structural analysis techniques, mainly linear algebraic ones. From the functional point of view the following properties are considered: boundedness, deadlock-freeness, liveness and the existence of home states. From the performance point of view the considered properties are marking ergodicity, computation of visit ratios and computation of insensitive throughput bounds.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/tscc-qmipsbook-95.pdf}, doi={10.1007/978-3-642-79917-4_4} } @INPROCEEDINGS{PJCS-95, author = {C.J. P{\'e}rez-Jim{\'e}nez and J. Campos and M. Silva}, title = {On Approximate Throughput Computation of Deterministic Systems of Sequential Processes}, booktitle = {Actas de las IV Jornadas de Concurrencia}, year = {1995}, pages = {156-171}, address = {El Escorial, Spain}, month = {June}, publisher = {Universidad Complutense de Madrid}, abstract = {We concentrate on a family of discrete event systems obtained from a simple modular design principle that include in a controlled way primitives to deal with concurrency, decisions, synchronization, blocking, and bulk movements of jobs. Due to the functional complexity of such systems, reliable throughput approximation algorithms must be deeply supported on a structure based decomposition technique. We present two complementary decomposition techniques and a fixed-point search iterative process based on response time preservation of subsystems. An extensive battery of numerical experiments has shown that the error is less than 3%, and that the state space is usually reduced by more than one order of magnitude.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/pjcs-95.pdf} } @INPROCEEDINGS{SC-Erlangen-95, author = {M. Silva and J. Campos}, title = {Structural Performance Analysis of Stochastic {Petri} Nets}, booktitle = {Proceedings of the IEEE International Computer Performance and Dependability Symposium}, year = {1995}, pages = {61-70}, address = {Erlangen, Germany}, month = {April}, publisher = {IEEE-Computer Society Press}, note = {Invited paper}, abstract = {Structure performance analysis theory and techniques is an essay to avoid the computational complexity problem associated to Markovian and discrete event simulation techniques. Even if a finished conceptual and technical framework is not yet available, important benefits have been obtained not only from performance but also from correctness analysis point of view. In this survey we overview some of the achievements developed by the authors and collaborators towards a structure theory for performance evaluation of net based models. Concepts and techniques for the computation of performance bounds and approximate and exact evaluation are described in a semi-formal/illustrative way through a selected collection of examples.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/sc-erlangen-95.pdf}, doi={10.1109/IPDS.1995.395816} } @INCOLLECTION{BBBCC-QMIPS-94, author = {F. Baccelli and G. Balbo and R.J. Boucherie and J. Campos and G. Chiola}, title = {Annotated Bibliography on Stochastic {Petri} Nets}, booktitle = {Performance Evaluation of Parallel and Distributed Systems: Solution Methods}, publisher = {Centrum voor Wiskunde en Informatica}, year = {1994}, editor = {O.J. Boxma and G.M. Koole}, volume = {105}, series = {Tract}, pages = {25-44}, address = {Amsterdam}, abstract = {An annotated bibliography on stochastic Petri nets is given.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/bbbcc-qmips-94.pdf}, doi={} } @INCOLLECTION{CCJS-QMIPS-94, author = {J. Campos and J.M. Colom and H. Jungnitz and M. Silva}, title = {A General Iterative Technique for Approximate Throughput Computation of Stochastic Marked Graphs}, booktitle = {Performance Evaluation of Parallel and Distributed Systems: Solution Methods}, publisher = {Centrum voor Wiskunde en Informatica}, year = {1994}, editor = {O.J. Boxma and G.M. Koole}, volume = {106}, series = {Tract}, pages = {265-283}, address = {Amsterdam}, abstract = {A general iterative technique for approximate throughput computation of stochastic strongly connected marked graphs is presented. It generalizes a previous technique based on net decomposition through a single input-single output cut, allowing the split of the model through any cut. The approach has two basic foundations. First, a deep understanding of the qualitative behaviour of marked graphs leads to a general decomposition technique. Second, after the decomposition phase, an iterative response time approximation method is applied for the computation of the throughput. Experimental results on several examples generally have an error of less than 3%. The state space is usually reduced by more than one order of magnitude; therefore the analysis of otherwise intractable systems is possible.}, doi={} } @INCOLLECTION{CCST-QMIPS-94, author = {J. Campos and J.M. Colom and M. Silva and E. Teruel}, title = {Functional and Performance Analysis of Cooperating Sequential Processes}, booktitle = {Performance Evaluation of Parallel and Distributed Systems: Solution Methods}, publisher = {Centrum voor Wiskunde en Informatica}, year = {1994}, editor = {O.J. Boxma and G.M. Koole}, volume = {106}, series = {Tract}, pages = {233-251}, address = {Amsterdam}, abstract = {This paper presents some results concerning the functional and performance analysis of sequential proceses connected through buffers using structural analysis techniques, mainly linear algebraic ones. From the functional point of view the following properties are considered: boundedness, deadlock-freeness, liveness and the existence of home states. From the performance point of view the considered properties are marking ergodicity, computation of visit ratios and computation of insensitive throughput bounds.}, doi={} } @INCOLLECTION{CACCS-QMIPS-94, author = {G. Chiola and C. Anglano and J. Campos and J.M. Colom and M. Silva}, title = {Operational Analysis of Timed {Petri} Nets and Application to the Computation of Performance Bounds}, booktitle = {Performance Evaluation of Parallel and Distributed Systems: Solution Methods}, publisher = {Centrum voor Wiskunde en Informatica}, year = {1994}, editor = {O.J. Boxma and G.M. Koole}, volume = {106}, series = {Tract}, pages = {197-213}, address = {Amsterdam}, abstract = {We use operational analysis techniques to partially characterize the behaviour of timed Petri nets under very weak assumptions on their timing semantics. New operational inequalities are derived that are typical of the presence of synchronization and that were therefore not considered in queueing network models. We show an interesting application of the operational laws to the statement and the efficient solution of problems related to the estimation of performance bounds insensitive to the timing probability distributions. The results obtained generalize and improve in a clear setting results that were derived in the last few years for several different subclasses of timed Petri nets. In particular the extension to Well-Formed Coloured nets appears straightforward and allows an efficient exploitation of models symmetries.}, doi={} } @ARTICLE{TSCC-LNCIS-94, author = {E. Teruel and M. Silva and J.M. Colom and J. Campos}, title = {Functional and Performance Analysis of Cooperating Sequential Processes}, journal = {Lecture Notes in Control and Information Sciences}, year = {1994}, volume = {199}, pages = {169-175}, abstract = {A class of Petri nets suitable for modelling sequential processes cooperating by means of message passing is presented. Some functional (boundedness, liveness, home states) and performance (ergodicity, computation of visit ratios and throughput bounds) aspects are considered from a structure theory perspective.}, address = {London}, booktitle = {Analysis and Optimization of Systems: Discrete Event Systems}, editor = {G. Cohen and J.P. Quadrat}, publisher = {Springer-Verlag}, doi={10.1007/BFb0033545} } @ARTICLE{CCJS-TSE-94, author = {J. Campos and J.M. Colom and H. Jungnitz and M. Silva}, title = {Approximate Throughput Computation of Stochastic Marked Graphs}, journal = {IEEE Transactions on Software Engineering}, year = {1994}, volume = {20}, pages = {526-535}, number = {7}, month = {July}, abstract = {A general iterative technique for approximate throughput computation of stochastic strongly connected marked graphs is presented. It generalizes a previous technique based on net decomposition through a single input-single output cut, allowing the split of the model through any cut. The approach has two basic foundations. First, a deep understanding of the qualitative behaviour of marked graphs leads to a general decomposition technique. Second, after the decomposition phase, an iterative response time approximation method is applied for the computation of the throughput. Experimental results on several examples generally have an error of less than 3%. The state space is usually reduced by more than one order of magnitude; therefore the analysis of otherwise intractable systems is possible.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/ccjs-tse-94.pdf}, doi={10.1109/32.297941} } @INCOLLECTION{State-of-the-art-93, author = {G. Balbo and M. Silva and G. Chiola and J. Campos and others}, title = {The Timed (Coloured) {Petri} Net Formalism: Position Paper}, booktitle = {Workshop on Formalisms, Principles, and State-of-the-Art}, publisher = {Arbeitsberichte des Instituts f{\"u}r Mathematische Maschinen und Datenverarbeitung (Informatik)}, year = {1993}, volume = {14}, series = {Band 26}, pages = {3-60}, address = {Erlangen, Germany}, abstract = {This paper presents the point of view of the groups of the universities of Torino and Zaragoza on the timed Petri net formalism. Coloured and non coloured models are covered at the same time, the latter making sense in case of systems without symmetries. We argue that Petri net formalisms allow more freedom than other established formalisms in the choices regarding the trade off between structural model complexity and interpretation of the graph. Some considerations are made on coloured Petri nets that could suggest them as a superior modelling formalism. The main comparison term that we selected are BCMP type queueing networks.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/state-of-the-art-93.pdf}, doi={} } @ARTICLE{CPSM-RMUCM-93, author = {J. Campos and B.F. Plo and San Miguel, M.}, title = {Boundedness on Stochastic {Petri} Nets}, journal = {Revista Matem{\'a}tica de la Universidad Complutense de Madrid}, year = {1993}, volume = {6}, pages = {123-136}, number = {1}, abstract = {Stochastic Petri nets generalize the notion of queueing systems and are a useful model in performance evaluation of parallel and distributed systems. We give necessary and sufficient conditions for the boundedness of a stochastic process related to these nets.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/cpsm-rmucm-93.pdf}, doi={} } @INPROCEEDINGS{CCCS-Roma-93, author = {G. Chiola and J. Campos and J.M. Colom and M. Silva}, title = {Operational Analysis of Timed {Petri} Nets}, booktitle = {Proceedings of the 16th International Symposium on Computer Performance Modelling, Measurement and Evaluation (Performance'93)}, year = {1993}, address = {Roma, Italy}, month = {September}, abstract = {Operational analysis is a conceptually very simple way of deriving mathematical equations relating measurable quantities in queueing systems [DB 78]. In [DC 92] the reader can find some nice examples of how the application of operational analysis techniques can help in explaining and proving fundamental results in queueing network analysis. Here we apply operational analysis techniques to derive linear equations and inequalities relating interesting performance measures in timed Petri net models. The main conceptual difference between queueing and Petri net models is the presence of a synchronization primitive in the latter. New operational inequalities are derived for synchronization elements that have no counterpart in operational laws for queueing networks. In addition to the mathematical interest of these derivations, the results can be immediately used for the computation of performance bounds based on linear programming techniques.}, doi={} } @INPROCEEDINGS{CCJS-Toulouse-93, author = {J. Campos and J.M. Colom and H. Jungnitz and M. Silva}, title = {A General Iterative Technique for Approximate Throughput Computation of Stochastic Marked Graphs}, booktitle = {Proceedings of the 5th International Workshop on Petri Nets and Performance Models}, year = {1993}, pages = {138-147}, address = {Toulouse, France}, month = {October}, publisher = {IEEE-Computer Society Press}, abstract = {A general iterative technique for approximate throughput computation of stochastic strongly connected marked graphs is presented. It generalizes a previous technique based on net decomposition through a single input-single output cut, allowing the split of the model through any cut. The approach has two basic foundations. First, a deep understanding of the qualitative behaviour of marked graphs leads to a general decomposition technique. Second, after the decomposition phase, an iterative response time approximation method is applied for the computation of the throughput. Experimental results on several examples generally have an error of less than 3%. The state space is usually reduced by more than one order of magnitude; therefore the analysis of otherwise intractable systems is possible.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/ccjs-toulouse-93.pdf}, doi={10.1109/PNPM.1993.393427} } @INPROCEEDINGS{CACCS-Toulouse-93, author = {G. Chiola and C. Anglano and J. Campos and J.M. Colom and M. Silva}, title = {Operational Analysis of Timed {Petri} Nets and Application to the Computation of Performance Bounds}, booktitle = {Proceedings of the 5th International Workshop on Petri Nets and Performance Models}, year = {1993}, pages = {128-137}, address = {Toulouse, France}, month = {October}, publisher = {IEEE-Computer Society Press}, abstract = {We use operational analysis techniques to partially characterize the behaviour of timed Petri nets under very weak assumptions on their timing semantics. New operational inequalities are derived that are typical of the presence of synchronization and that were therefore not considered in queueing network models. We show an interesting application of the operational laws to the statement and the efficient solution of problems related to the estimation of performance bounds insensitive to the timing probability distributions. The results obtained generalize and improve in a clear setting results that were derived in the last few years for several different subclasses of timed Petri nets. In particular the extension to Well-Formed Coloured nets appears straightforward and allows an efficient exploitation of models symmetries.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/caccs-toulouse-93.pdf}, doi={10.1109/PNPM.1993.393428} } @INPROCEEDINGS{RCS-Atlanta-93, author = {A. Ram{\'{\i}}rez and J. Campos and M. Silva}, title = {On Optimal Scheduling in {DEDS}}, booktitle = {Proceedings of the 1993 IEEE International Conference on Robotics and Automation}, year = {1993}, pages = {821-826}, address = {Atlanta, USA}, month = {May}, abstract = {In this paper we present the Local Optimality (LO) property for Discrete Event Dynamic Systems modeled using Petri Nets (PN's). If a system is divided into independent subsystems and if the optimal behaviour of these subsystems guarantees the optimal behaviour of whole system, then this system possesses the LO property. The main advantage of this approach is that we can find an optimal schedule for this class of systems in less time, because we are determining the optimal behaviour of small problems. A characterization of systems exhibiting the LO property is given, as well as one procedure to divide them into subsystems.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/rcs-atlanta-93.pdf}, doi={10.1109/ROBOT.1993.292246} } @ARTICLE{CS-PE-93, author = {J. Campos and M. Silva}, title = {Embedded Product-Form Queueing Networks and the Improvement of Performance Bounds for {Petri} Net Systems}, journal = {Performance Evaluation}, year = {1993}, volume = {18}, pages = {3-19}, number = {1}, month = {July}, abstract = {This paper addresses the computation of upper bounds for the steady-state throughput of stochastic Petri net systems with immediate and generally distributed timed transitions. It is achieved through the use of a kind of decomposition of the whole net system. Results are obtained deeply bridging stochastic Petri net theory to untimed Petri net and queueing network theories. Previous results are improved by considering some embedded product-form queueing networks (generated by the support of some left annullers of the incidence matrix of the net). The obtained results for the case of live and bounded free choice systems are of special interest. In this case, the subnets generated by the minimal left annullers of the incidence matrix always have a topology of product-form closed monoclass queueing networks.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/cs-pe-93.pdf}, doi={10.1016/0166-5316(93)90024-O} } @INPROCEEDINGS{SC-Brussels-93, author = {M. Silva and J. Campos}, title = {Performance Models Based on {Petri} Nets}, booktitle = {Proceedings of the IMACS/IFAC Second International Symposium on Mathematical and Intelligent Models in System Simulation}, year = {1993}, pages = {xiv-xxi}, month = {April}, publisher = {Brussels, Belgium}, note = {Invited paper}, abstract = {Petri Nets (PNs) is a well suited formalism to model and analyze parallel and distributed discrete event dynamic systems. Provided with adequate timed interpretation, PNs allow to build performance models in which true concurrence can be described together with synchronization and sharing phenomena. This survey paper gives a fast overview of some major topics related to net performance models, obtained through stochastically timed interpretation of PNs. Analysis of net models, pointing out the importance of the logical and performance perspectives, and some relations between queueing networks and PN models are briefly considered.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/sc-brussels-93.pdf}, doi={} } @INCOLLECTION{CCS-RFMS-92, author = {J. Campos and J.M. Colom and M. Silva}, title = {Improving Throughput Upper Bounds for Net Based Models of Manufacturing Systems}, booktitle = {Robotics and Flexible Manufacturing Systems}, publisher = {Elsevier Science Publishers B.V. (North-Holland)}, year = {1992}, editor = {J.C. Gentina and S.G. Tzafestas}, pages = {281-294}, address = {Amsterdam, The Netherlands}, abstract = {This paper addresses the improvement of throughput upper bounds for live and bounded stochastic Petri nets, presented by the authors in previous works. The introduction of a greater amount of structural information, traps and implicit places, allows to improve the bounds using linear programming problems defined on the net structure, on the routing probabilities, and on the mean service time of transitions. The obtained bounds can be applied for the analysis of manufacturing systems modelled by means of stochastic Petri nets. An example is presented and evaluated using the introduced techniques.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/ccs-rfms-92.pdf}, doi={} } @ARTICLE{CS-LNCS-92, author = {J. Campos and M. Silva}, title = {Structural Techniques and Performance Bounds of Stochastic {Petri} Net Models}, journal = {Lecture Notes in Computer Science}, year = {1992}, volume = {609}, pages = {352-391}, abstract = {In this paper we overview some recent results obtained by the authors and collaborators on the performance bounds analysis of some stochastic Petri net systems. The mathematical model can be seen either as a result of the addition of a particular random timing interpretation to an "autonomous'' Petri net or as a generalization of classical queueing networks with the addendum of a general synchronization primitive. It constitutes an adequate tool for both the validation of logical properties and the evaluation of performance measures of concurrent and distributed systems. Qualitative and quantitative understandings of Petri net models are stressed here making special emphasis on structural techniques for the analysis of logical and performance properties. Important aspects from the performance point of view, such as relative throughput of stations (transitions), and number of servers present at them, are related to Petri net concepts like P- or T-semiflows or liveness bounds of transitions. For the particularly interesting case of Markovian Petri net systems, some improvements of the bounds can be achieved. Marked graphs and free choice are net subclasses for which the obtained results have special quality, therefore an additional attention is focussed on them.}, address = {Berlin}, booktitle = {Advances in Petri Nets 1992}, editor = {G. Rozenberg}, publisher = {Springer-Verlag}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/cs-lncs-92.pdf}, doi={10.1007/3-540-55610-9_178} } @INCOLLECTION{SCC-Mita-91, author = {M. Silva and J.M. Colom and J. Campos}, title = {Linear Algebraic Techniques for the Analysis of {Petri} Nets}, booktitle = {Recent Advances in Mathematical Theory of Systems, Control, Networks, and Signal Processing II}, publisher = {Mita Press}, year = {1992}, pages = {35-42}, address = {Tokyo, Japan}, abstract = {One of the indigenous techniques for the analysis of Petri Net system models is based on its non-negative state equation, bridging convex goemetry and linear programming theories to the theory of Petri Nets. This invited survey briefly overviews some recent developments in the use of linear algebraic techniques for the qualitative (i.e., logical) and quantitative (i.e., performance) analysis of Petri Net system models, dealing with properties like deadlock-freeness, structural liveness or throughput bounds.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/scc-mita-91.pdf}, doi={} } @ARTICLE{CCCS-CAS-92, author = {J. Campos and G. Chiola and J.M. Colom and M. Silva}, title = {Properties and Performance Bounds for Timed Marked Graphs}, journal = {IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications}, year = {1992}, volume = {39}, pages = {386-401}, number = {5}, month = {May}, abstract = {A class of synchronized queueing networks with deterministic routing is identified to be equivalent to a subclass of timed Petri nets called marked graphs. First some structural and behavioral properties of marked graphs are recalled and used to show interesting properties of this class of performance models. In particular, ergodicity is derived from boundedness and liveness of the underlying Petri net representation, which can be efficiently computed in polynomial time on the net structure. In case of unbounded (i.e., non-strongly-connected) marked graphs, ergodicity is computed as a function of the average transition firing delays. Then the problem of computing both upper and lower bounds for the steady-state performance of timed and stochastic marked graphs is studied. In particular, linear programming problems defined on the incidence matrix of the underlying Petri nets are used to compute tight (i.e., attainable) bounds for the throughput of transitions for marked graphs with deterministic or stochastic time associated with transitions. These bounds depend on the initial marking and the mean values of the delays but not on the probability distribution functions (thus including both the deterministic and the stochastic cases). The benefits of interleaving qualitative and quantitative analysis of marked graph models are shown.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/cccs-cas-92.pdf}, doi={10.1109/81.139289} } @INCOLLECTION{C-DEMON-91, author = {J. Campos}, title = {Performance Analysis of Live and Bounded Free Choice Systems}, booktitle = {Design Methods Based on Nets}, year = {1991}, editor = {E. Best and J. Esparza}, series = {GMD-Studien Nr. 198}, pages = {38-48}, address = {Sankt Augustin, Germany}, month = {September}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/c-demon-91.pdf}, doi={} } @INPROCEEDINGS{CCS-Lille-91, author = {J. Campos and J.M. Colom and M. Silva}, title = {Improving Throughput Upper Bounds for Net Based Models}, booktitle = {Proceedings of the IMACS-IFAC International Symposium on Modeling and Control of Technological Systems}, year = {1991}, pages = {573-582}, address = {Lille, France}, month = {May}, abstract = {This paper addresses the improvement of throughput upper bounds for live and bounded stochastic Petri nets, presented by the authors in previous works. The introduction of a greater amount of structural information, traps and implicit places, allows to improve the bounds using linear programming problems defined on the net structure, on the routing probabilities, and on the mean service time of transitions. The obtained bounds can be applied for the analysis of manufacturing systems modelled by means of stochastic Petri nets. An example is presented and evaluated using the introduced techniques.}, doi={} } @INPROCEEDINGS{CC-Gjern-91, author = {J. Campos and J.M. Colom}, title = {A Reachable Throughput Upper Bound for Live and Safe Free Choice Nets}, booktitle = {Proceedings of the Twelfth International Conference on Application and Theory of Petri Nets}, year = {1991}, pages = {237-256}, address = {Gjern, Denmark}, month = {June}, organization = {EATCS}, publisher = {IBM Deutschland}, abstract = {This paper addresses the computation of upper bounds for the throughput of transitions of live and safe deterministically or stochastically timed free choice nets. The obtained results are extensions of the marked graph case, presented by the authors in previous works. Polynomial complexity algorithms are derived using linear programming techniques. The obtained values are tight in the sense that, with the only knowledge of the net topology, the mean service times of transitions, and the routing rates at conflicts, is not possible to improve the bounds.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/cc-gjern-91.pdf}, doi={} } @INPROCEEDINGS{SCC-Kobe-91, author = {M. Silva and J.M. Colom and J. Campos}, title = {Linear Algebraic Techniques for the Analysis of {Petri} Nets}, booktitle = {Proceedings of the International Symposium on the Mathematical Theory of Networks and Systems}, year = {1991}, pages = {413-415}, address = {Kobe, Japan}, month = {June}, abstract = {One of the indigenous techniques for the analysis of Petri Net system models is based on its non-negative state equation, bridging convex goemetry and linear programming theories to the theory of Petri Nets. This invited survey briefly overviews some recent developments in the use of linear algebraic techniques for the qualitative (i.e., logical) and quantitative (i.e., performance) analysis of Petri Net system models, dealing with properties like deadlock-freeness, structural liveness or throughput bounds.}, doi={} } @ARTICLE{CCS-TSE-91, author = {J. Campos and G. Chiola and M. Silva}, title = {Ergodicity and Throughput Bounds of {Petri} Nets with Unique Consistent Firing Count Vector}, journal = {IEEE Transactions on Software Engineering}, year = {1991}, volume = {17}, pages = {117-125}, number = {2}, month = {February}, abstract = {This paper addresses ergodicity and throughput bounds characterizations for a subclass of timed and stochastic Petri nets, interleaving qualitative and quantitative theories. The considered nets represent an extension of the well known subclass of marked graphs, defined as having a unique consistent firing count vector, independently of the stochastic interpretation of the net model. In particular, persistent and mono-T-semiflow nets subclasses are considered. Upper and lower throughput bounds are computed using linear programming problems defined on the incidence matrix of the underlying net. The bounds proposed here depend on the initial marking and the mean values of the delays but not on the probability distributions (thus including both the deterministic and the stochastic cases). From a different perspective, the considered subclasses of stochastic nets can be viewed as special classes of synchronized queueing networks, thus the proposed bounds can be applied to these networks.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/ccs-tse-91.pdf}, doi={10.1109/32.67593} } @ARTICLE{CCS-TAC-91, author = {J. Campos and G. Chiola and M. Silva}, title = {Properties and Performance Bounds for Closed Free Choice Synchronized Monoclass Queueing Networks}, journal = {IEEE Transactions on Automatic Control}, year = {1991}, volume = {36}, pages = {1368-1382}, number = {12}, month = {December}, abstract = {Several proposals exist for the introduction of synchronization constraints into Queueing Networks (QN). We show that many monoclass QN with synchronizations can naturally be modelled with a subclass of Petri Nets (PN) called Free Choice nets (FC), for which a wide gamut of qualitative behavioural and structural results have been derived. We use some of these net theoretic results to characterize the ergodicity, boundedness and liveness of closed Free Choice Synchronized Queueing Networks (FCSQN). Moreover we define upper and lower throughput bounds based on the mean value of the service times, without any assumption on the probability distributions (thus including both the deterministic and the stochastic cases). We show that monotonicity properties exist between the throughput bounds and the parameters of the model in terms of population and service times. We propose (theoretically polynomial and practically linear complexity) algorithms for the computation of these bounds, based on linear programming problems defined on the incidence matrix of the underlying FC net. Finally, using classical laws from queueing theory, we provide bounds for mean queue lengths and response time.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/ccs-tac-91.pdf}, doi={10.1109/9.106153} } @INPROCEEDINGS{CS-Melbourne-91, author = {J. Campos and M. Silva}, title = {Throughput Upper Bounds for {Markovian} {Petri} Nets: Embedded Subnets and Queueing Networks}, booktitle = {Proceedings of the 4rd International Workshop on Petri Nets and Performance Models}, year = {1991}, pages = {312-321}, address = {Melbourne, Australia}, month = {December}, publisher = {IEEE-Computer Society Press}, abstract = {This paper addresses the computation of upper bounds for the steady-state throughput of stochastic Petri nets with immediate and exponentially distributed service times of transitions. We try to deeply bridge stochastic Petri net theory to untimed Petri net and queueing network theories. Previous results for general service time distributions are improved for the case of Markovian nets by considering the slowest embedded subnet (generated by the support of left annullers of the incidence matrix of the net). The obtained results for the case of live and bounded free choice nets are of special interest. For such nets, the subnets generated by the left annullers of the incidence matrix can be seen as embedded product-form closed monoclass queueing networks, and efficient algorithms exist for their analysis.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/cs-melbourne-91.pdf}, doi={10.1109/PNPM.1991.238789} } @INPROCEEDINGS{CSS-Melbourne-91, author = {J. Campos and B. S{\'a}nchez and M. Silva}, title = {Throughput Lower Bounds for {Markovian} {Petri} Nets: Transformation Techniques}, booktitle = {Proceedings of the 4rd International Workshop on Petri Nets and Performance Models}, year = {1991}, pages = {322-331}, address = {Melbourne, Australia}, month = {December}, publisher = {IEEE-Computer Society Press}, abstract = {This paper addresses the computation of lower bounds for the steady- state throughput of stochastic Petri nets with immediate and exponentially distributed service times of transitions. We try to deeply bridge stochastic Petri net theory to untimed Petri net and queueing networks theories. Previous results for general service time distributions are improved for the case of Markovian nets by considering some pessimistic transformation rules operating locally on the net structure, its initial marking, and stochastic interpretation. Special interest have the obtained results for the case of live and bounded free choice nets and live marked graphs systems.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/css-melbourne-91.pdf}, doi={10.1109/PNPM.1991.238788} } @INCOLLECTION{CS-DS-90, author = {J. Campos and M. Silva}, title = {Steady-State Performance Evaluation of Totally Open Systems of {Markovian} Sequential Processes}, booktitle = {Decentralized Systems}, publisher = {Elsevier Science Publishers B.V. (North-Holland)}, year = {1990}, editor = {M. Cosnard and C. Girault}, pages = {427-438}, address = {Amsterdam, The Netherlands}, abstract = {Totally open systems of Markovian sequential processes are defined as a subclass of stochastic Petri nets. They can be viewed as a generalization of a subclass of queueing networks in which complex sequential servers can be synchronized according to some particular schemes. Structural analysis of these nets is considered for avoiding the state explotion problem of the embedded Markov chain. Some qualitative properties interesting from a performance point of view are presented. In particular, a "potential ergodicity'' property is characterized by means of two structural properties: consistency and synchronic distance relation. Necessary and sufficient ergodicity conditions and the computation of steady-state performance measures are studied.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/cs-ds-90.pdf}, doi={} } @PHDTHESIS{Campos-thesis-90, author = {J. Campos}, title = {Performance Bounds for Synchronized Queueing Networks}, school = {Departamento de Ingenier{\'{\i}}a El{\'e}ctrica e Inform{\'a}tica, Universidad de Zaragoza, Spain}, year = {1990}, address = {Research Report GISI-RR-90-20}, month = {October}, abstract = {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 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 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 mono-T-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 FRT-nets, 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. 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.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/campos-thesis-90.pdf}, doi={} } @INPROCEEDINGS{CCS-Rensselaer-90, author = {J. Campos and J.M. Colom and M. Silva}, title = {Performance Evaluation of Repetitive Automated Manufacturing Systems}, booktitle = {Proceedings of the Rensselaer's Second International Conference on Computer Integrated Manufacturing}, year = {1990}, pages = {74-81}, address = {Rensselaer Polytechnic Institute, Troy, NY, USA}, month = {May}, publisher = {IEEE-Computer Society Press}, abstract = {Steady-state performance evaluation of some repetitive automated manufacturing systems modelled by means of stochastic or deterministic timed Petri nets is considered. Basically, concepts and techniques developed by the authors in other works are applied to repetitive manufacturing systems in this paper. Linear programming problems defined on the incidence matrix of the underlying Petri nets are used to compute tight upper and lower bounds for the performance measures of job-shop systems and decision-free kanban systems in polynomial time on the net structure. The results can be extended to other models in which some decisions are allowed, such as producer-consumer systems with mutual exclusion. Exact performance measures for a class of systems containing sequential processes can be computed in polynomial time.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/ccs-rensselaer-90.pdf}, doi={10.1109/CIM.1990.128074} } @INPROCEEDINGS{CCS-DEMON-90, author = {J.M. Colom and J. Campos and M. Silva}, title = {On liveness analysis through linear algebraic techniques}, booktitle = {Proceedings of the Annual General Meeting of ESPRIT Basic Research Action 3148 Design Methods Based on Nets (DEMON)}, year = {1990}, address = {Paris, France}, month = {June}, abstract = {Proving properties of Place/Transition Nets through Linear Algebraic Techniques is very interesting because of the polynomial complexity of the algorithms used for this purpose. In this sense, many works have been devoted to the linear analysis of marking related properties (e.g. boundedness of the state space, mutual exclusions, etc.). Nevertheless, few results exist related to linear analysis of liveness properties. In this note, we investigate some applications of linear techniques to partial characterization of liveness properties. First, a necessary condition for structural liveness in structural bounded nets is presented. It is based on the rank of the incidence matrix. Finally, given an initial marking, some sufficient conditions for dead transitions and for deadlock-freeness are presented.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/ccs-demon-90.pdf} } @INPROCEEDINGS{CCCS-Kyoto-89, author = {J. Campos and G. Chiola and J.M. Colom and M. Silva}, title = {Tight Polynomial Bounds for Steady-State Performance of Marked Graphs}, booktitle = {Proceedings of the 3rd International Workshop on Petri Nets and Performance Models}, year = {1989}, pages = {200-209}, address = {Kyoto, Japan}, month = {December}, publisher = {IEEE Computer Society Press}, abstract = {The problem of computing both upper and lower bounds for the steady-state performance of timed and stochastic Marked Graphs is studied. In particular, Linear Programming problems defined on the incidence matrix of the underlying Petri nets are used to compute tight (i.e., reachable) bounds for the throughput of transitions for live and bounded Marked Graphs with time associated with transitions. These bounds depend on the initial marking and the mean values of the delays but not on the probability distributions (thus including both the deterministic and the stochastic cases). Connections between results and techniques typical of qualitative and quantitative analysis of Petri models are stressed.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/cccs-kyoto-89.pdf}, doi={10.1109/PNPM.1989.68553} } @INPROCEEDINGS{CCS-Kyoto-89, author = {J. Campos and G. Chiola and M. Silva}, title = {Properties and Steady-State Performance Bounds for {Petri} Nets with Unique Repetitive Firing Count Vector}, booktitle = {Proceedings of the 3rd International Workshop on Petri Nets and Performance Models}, year = {1989}, pages = {210-220}, address = {Kyoto, Japan}, month = {December}, publisher = {IEEE Computer Society Press}, abstract = {The problem of computing both upper and lower bounds for the steady-state performance of timed and stochastic Petri nets is studied. In particular, Linear Programming problems defined on the incidence matrix of underlying Petri net are used to compute bounds for the throughput of transitions for live and bounded nets with a unique possibility of steady-state behaviour. These classes of nets are defined and their characteristics are studied. The bounds proposed here depend on the initial marking and the mean values of the delays but not on the probability distributions (thus including both the deterministic and the stochastic cases); moreover they can be computed also for non-ergodic models. Connections between results and techniques typical of qualitative and quantitative analysis of Petri models are stressed.}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/ccs-kyoto-89.pdf}, doi={10.1109/PNPM.1989.68554} } @INPROCEEDINGS{CS-Lyon-89, author = {J. Campos and M. Silva}, title = {Steady-State Performance Evaluation of Totally Open Systems of {Markovian} Sequential Processes}, booktitle = {Proceedings of the Working Conference on Decentralized Systems}, year = {1989}, pages = {559-585}, address = {Lyon, France}, month = {December}, publisher = {International Federation for Information Processing W.G.~10.3}, abstract = {Totally open systems of Markovian sequential processes are defined as a subclass of stochastic Petri nets. They can be viewed as a generalization of a subclass of queueing networks in which complex sequential servers can be synchronized according to some particular schemes. Structural analysis of these nets is considered for avoiding the state explotion problem of the embedded Markov chain. Some qualitative properties interesting from a performance point of view are presented. In particular, a "potential ergodicity'' property is characterized by means of two structural properties: consistency and synchronic distance relation. Necessary and sufficient ergodicity conditions and the computation of steady-state performance measures are studied.}, doi={} }