%0 Journal Article %1 CCCS-CAS-92 %A Campos, J. %A Chiola, G. %A Colom, J.M. %A Silva, M. %D 1992 %J IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications %K imported %N 5 %P 386-401 %R 10.1109/81.139289 %T Properties and Performance Bounds for Timed Marked Graphs %U http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/cccs-cas-92.pdf %V 39 %X 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.

@article{CCCS-CAS-92, 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.}, added-at = {2017-05-12T16:10:55.000+0200}, author = {Campos, J. and Chiola, G. and Colom, J.M. and Silva, M.}, biburl = {https://www.bibsonomy.org/bibtex/28fe66f9a3b477ccbd2e9b56df4b3962e/jcampos}, doi = {10.1109/81.139289}, interhash = {c02ee487279f2f87bede1b86aeb1a226}, intrahash = {8fe66f9a3b477ccbd2e9b56df4b3962e}, journal = {IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications}, keywords = {imported}, month = May, number = 5, pages = {386-401}, timestamp = {2017-05-12T16:10:55.000+0200}, title = {Properties and Performance Bounds for Timed Marked Graphs}, url = {http://webdiis.unizar.es/~jcampos/wordpress/wp-content/plugins/papercite/pdf/cccs-cas-92.pdf}, volume = 39, year = 1992 }