Les réseaux de Petri (datants de 1962) constituent un outil très bien adapté à la modélisation et l'analyse de systèmes complexes présentant de la concurrence et de la synchronisation. Les réseaux de Petri ont été introduits dans les années 70 afin de décrire le comportement global des systèmes complexes au cours du temps. Plus tard, en 1980, ont étés introduits les réseaux de Petri stochastiques ou le temps de séjour dans différents états était aléatoires (et suivait une loi exponentielle). Le système était alors analysé à l'aide d'une chaîne de Markov. L'extension suivante a étée l'introduction de transitions immédiates tel que le séjour dans un état pouvait être nul (ces réseaix étaient appelés réseaux de Petri stochastiques généralisés). Là encore, l'analyse se faisait par l'étude de la chaîne de Markov sous-jacente. L'extension suivante, qui constitue le type de réseau de Petri que nous étudions, consiste à considérer des lois générales pour les temps de transition, ainsi que des disciplines de rééchantillonnage variées (PRD, PRS, PRI). La dernière extension est l'ajout de composantes fluides au modèle afin de pouvoir modéliser les éléments physiques continus mais aussi d'approcher de nombreux éléments discrets par du fluide pour diminuer le nombre d'événements à traiter.
Différentes méthodes sont possibles pour analyser ces modèles:
Une analyse analytique quand le processus stochastique sous-jascent est une chaîne de Markov et que l'espace d'états reste mesuré.
Des méthodes d'analyse numérique si l'espace d'états est important (mais tout de même assez restreint pour pouvoir générer le graphe du processus sous-jascent).
Des méthodes de simulation dans le cas ou les méthodes précédentes ne sont pas applicables.
De nombreux outils d'analyse sont disponibles (voir par exemple le lien sur une liste d'outils en fin de page). A titre d'exemple, SPNP (pour Stochastic Petri Net Package), sur lequel j'ai pu travailler à l'Université de Duke, est un logiciel basé sur une extension du langage C incluant des primitives qui facilitent la description des réseaus de Petri stochastiques et de toutes leurs extensions (discrètes et fluides). Une interface graphique permet une utilisation simplifiée du système.
Mes travaux passés
Mes travaux sur l'analyse des réseaux de Petri ont étés les suivants (réalisés principalement au cours d'un séjour à Duke University):
Développement du simulateur de SPNP, avec notamment une extension de la capacité de modélisation (choix de distributions pour les transitions...) et l'intégration de nouvelles méthodes de simulation (importance sampling, importance splitting...)
Comparaison des réseaux de Petri stochastiques fluides avec les systèmes hybrides utilisés en théorie du contrôle.
Utilisation des réseaux de Petri stochastiques (fluides ou non) pour l'analyse des
files d'attente à seuils avec hystérésis.
Les sujets sur lesquels je compte continuer à travailler
Continuer l'intégration de méthodes de simulation à SPNP pour en faire un des simulateurs les plus performants.
Modélisation et analyse de protocoles Internet à l'aide de réseaux de Petri stochastiques, fluides ou non.
Modélisation et analyse des réseaux radiomobiles de troisième génération.
B. Tuffin and K.S. Trivedi. Implementation of Importance Splitting techniques in Stochastic Petri Net Package. In Haverkort, B.R., and Bohnenkamp, H.C. and Smith, C.U. (eds), Computer performance evaluation: Modelling tools and techniques; 11th International Conference; TOOLS 2000, Lecture Notes in Computer Science, volume 1786, Springer Verlag, pages 216-229, 2000.
C. Hirel, B. Tuffin and K.S. Trivedi. SPNP Version 6.0. In Haverkort , B.R., and Bohnenkamp, H.C. and Smith, C.U. (eds), Computer performance evaluation: Mode lling tools and techniques; 11th International Conference; TOOLS 2000, Lecture Notes in Computer Science, volume 1786, Springer Verlag, pages 354-357, 2000.
B. Tuffin, D.S. Chen and K.S. Trivedi. Comparison of Hybrid Systems and Fluid Stochastic Petri Nets. Discrete Event Dynamic Systems, 11 (1-2), 2001.
B. Tuffin and K.S. Trivedi. Importance Sampling for the Simulation of Stochastic Petri Nets and Fluid Stochastic Petri Nets. In Proceedings of High Performance Computing, 2001.
li> B. Tuffin and L.M. Le Ny. Modeling and analysis of threshold
queues with hysteresis using stochastic Petri nets: the monoclass case.
In Proceedings of Petri Nets and Performance Models, PNPM'01,
pages 175-184, IEEE CS Press, Aachen, Germany, 2001.
L.M. Le Ny and B. Tuffin. Modeling and analysis of multi-class
threshold-based queues with hysteresis using Stochastic Petri
Nets. In Proceedings the International Conference on Applications and
Theory of Petri Nets. Lecture Notes in Computer Science, Springer
Verlag, 2002.
Quelques Références bibliographiques
Reisig, W., Petri Nets: An introduction. Springer-Verlag, 1985.
Merlin, P.M and Farber, D.J., Recoverability of Communication Protocols: implications of a theoretical study, IEEE Transactions on Communications, 24(9)/1036-1043, 1976.
Symons, F.J.W., Introduction to Numerical Petri Nets: a General Graphical Model of Concurrent processing Systems, Australian Telecommunications Research, 14(1):28-33, 1980.
Ciardo, G. and Muppala, J; and Trivedi, K.S., On the Solution of GSPN Rewrd Models, Performance Evaluation , 12(4):237-253, 1991.
Ciardo, G. and Muppala, J; and Trivedi, K.S., SPNP: Stochastic Petri Net Package, In International Conference on Petri Nets and Performance Models , 1989.
Kulkarni, V.G. and Trivedi, K.S., FSPNs: Fluid Stochastic Petri Nets. In 14th International Conference on Applications and Theory of Petri Nets, pages 24-31, 1993.
Horton, G., Kulkarni, V.G. and Trivedi, K.S., Fluid Stochastic Petri Nets: Theorry, Application and Solution. European Journal of Operational Research, 105: 184-201, 1998.
Ciardo, G., Dinol, D.M. and Trivedi, K.S., Disrete-Event Simulation of Fluid Stochastic Petri Nets, IEEE Transactions on software engineering, 25 (2): pages 207-217, 1999.