Calcul des Réseaux Stochastiques

La recherche décrite dans cette page concerne l'étude des systèmes dynamiques à événements discrets aléatoires et notamment les réseaux stochastiques, la théorie des files d'attente et les réseaux de Petri (voir aussi la bibliographie sur les réseaux de Petri).

Nous nous sommes concentrés sur le développement d'un cadre algébrique permettant une représentation mathématique de certaines classes de réseaux indépendamment de leur dimension et des hypothèses stochastiques retenues dans leur modélisation. Ce formalisme permet d'unifier l'étude de plusieurs classes de réseaux de Petri comme par exemple les graphes d'événements ou les réseaux à choix libre. Ces classes contiennent elles-mêmes des réseaux classiques de la littérature comme par exemple les réseaux de Jackson généralisées. Cette représentation permet de concevoir de nouveaux mécanismes de contrôle de ces réseaux et d'évaluer analytiquement leurs performances par des méthodes tout à fait différentes de l'approche markovienne. Pour en savoir plus sur cette approche, on pourra consulter l’ouvrage initialement publié chez Wiley intitulé Synchronization andLinearity, que nous avons écrit avec G. Cohen, G. J. Olsder et J. P. Quadrat en 1992.

Voici mes principaux domaines d'intérêt actuels, qui sont également récapitulés dans les diapositives d'une conférence que j'ai donnée à la 10ème conférence de probabilités appliquées d'Ulm en Allemagne en juillet 1999 :

  • ANALYSE STOCHASTIQUE : une question importante dans ce contexte est celle du calcul et de la caractérisation analytique des distributions stationnaires des réseaux. Voici les directions principales:
    • DÉVELOPPEMENTS ANALYTIQUES pour les débits. Le but est d'établir des développements analytiques pour le débit de réseaux fermés avec des services aléatoires. Ces débits sont représentés comme des exposants de Lyapunov de produits de matrices aléatoire dans le semi-anneau (max, plus). Ces question sont traitées dans les rapports de recherche RR-3427 et RR-3558 écrits avec D. Hong .
    • ESTIMATIONS DES DISTRIBUTIONS dans les systèmes (max,plus) linéaires : Ces travaux concernent les réseaux ouverts dont les entrées sont des processus ponctuels de Poisson; le but est d'obtenir des expressions pour la loi des temps d'attente stationnaires ou transitoires. Les valeurs moyennes sont étudiées dans RR-2494 qui est un travail en commun avec V. Schmidt. Les transformées de Laplace sont traitées dans RR-2785 et RR-3022, avec V. Schmidt et S. Hasenfuss de l'université d'Ulm.
    • ASYMPTOTIQUE À QUEUES LOURDES pour les distributions stationnaires dans diverses classes des réseaux :
      • le cas des réseaux (max, plus) linéaires irréductibles est traité dans l'article de Questa 99 en collaboration avec V. Schmidt et S. Schlegel.
      • Le cas des réseaux monotones-séparables (voir ci-dessous) est étudié dans le RR-4197, en collaboration avec S. Foss ; dans cet article (maintenant publié dans les Annales de Probabilités Appliquées), nous avons commencé à développer la théorie des événements rares pour ces réseaux et nous avons traité quelques exemples; en particulier nous avons donné l'asymptotique exacte pour les files d'attente en tandem avec des temps de service sous-exponentiels.
      • Les asymptotiques des réseaux (max, plus) linéaires généraux avec des distributions de service sous-exponentielles ont été ensuite été traitées dans le RR-4952 et celles des réseaux de Jackson généralisés dans RR-5081, en collaboration avec S. Foss et M. Lelarge .
      Cette approche a des développements très intéressants qui mènent à une théorie de plus en plus complète pour l'analyse des événements rares dans les réseaux stochastiques. Un exposé des avancées sur ces questions peut être trouvé dans la thèse (soutenue en 2005) et la page Web de Marc Lelarge .
  • ALGÈBRE : nous avons travaillé sur le cadre algébrique permettant d'étudier les systèmes linéaires non homogènes dans le RR-3435 en commun avec R. Agrawal, de l'université du Wisconsin et R. Rajan, des laboratoires de AT&T. Une de nos motivations pour ceci est la modélisation des réseaux à intégration de service.
  • RÉSEAUX NON LINÉAIRES : au-delà des classes linéaires, il existe plusieurs autres classes de réseaux qui peuvent être analysés par l'intermédiaire de certains prolongements de ce cadre algébrique. Les principaux résultats concernent :
    • LE CADRE MONOTONE-SÉPARABLE que nous avons introduit avec S. Foss dans l'article du JAP 95. Cette classe contient comme cas particuliers les réseaux de Jackson généralisés, les réseaux (max, plus) linéaires, les files d'attente multiserveurs et plusieurs classes de réseaux de Petri stochastiques à choix libre.
    • SYSTÈMES (max, plus) LINÉAIRES AVEC DES PERTURBATIONS FIFO : le rapport RR-3434 avec T. Bonald concerne l'analyse de la région de stabilité pour le protocole TCP.
    • RÉSEAUX À CHOIX LIBRE : nous avons étudié cette classe dans le RR-2411 avec S. Foss et B. Gaujal ;
    • LES OPÉRATEURS NON EXPANSIFS permettent de représenter de nombreuses classes de réseaux. Voir le RR-2641, avec J. Mairesse du Liafa.
  • SIMULATION : notre contribution principale concerne la simulation parallèle des graphes d'événements stochastiques (voir le RR-1520 avec M. Canales). Pour l'extension aux réseaux à choix libre et à d'autres classes plus générales, cf. les pages de N. Furmento , B. Gaujal et A. Jean-Marie-Marie .

Notre groupe de recherche était associé du projet européen Alapedes qui faisait partie du programme TMR . Une université d’été sur ces sujets a également été organisée à Noirmoutier sur le thème Algèbres (max,plus) et applications en informatique et en automatique. Les développements récents de la théorie et plusieurs domaines d'application (notamment en productique, systèmes de transport, et informatique) y ont été traités.

Plusieurs types d'applications ont aussi été étudiées :

·        Contrôle de transmission dans les réseaux de communication.

·        Mécanismes de synchronisation dans le calcul parallèle (cf. le livre de Qmips , que nous avons co-édité avec A. Jean-Marie-Marie et I. Mitrani, qui récapitule les résultats que nous avons obtenus dans le cadre du projet européen BRA sur ce sujet).

·        Kanban et chaînes de production (voir par exemple le RR-2494 ).

·        Systèmes temps réel (voir le RR-3778 avec B. Gaujal et D. Simon ).

A. Jean-Marie a développé un prototype de logiciel appelé ERS qui permet de manipuler certains de ces objets et bien d'autres.