Réseaux de files d'attente

Un réseau de files d'attente relie plusieurs stations de service de sorte que les clients quittant une station se dirigent vers une autre ; il est remarquable que de nombreux réseaux de ce type possèdent un équilibre de forme produit qui se factorise à travers les stations.

Definition

Un réseau de files d'attente est un ensemble de stations de service interconnectées à travers lesquelles les clients se déplacent selon des probabilités de routage, et son analyse vise à déterminer la distribution stationnaire conjointe des nombres de clients dans toutes les stations, laquelle, sous de larges conditions, se factorise en un produit de termes propres à chaque station.

Scope

Ce sujet couvre les réseaux de files d'attente ouverts et fermés, les probabilités de routage et les équations de trafic, le théorème de Jackson sur la distribution stationnaire de forme produit des réseaux markoviens ouverts, l'extension BCMP aux classes de clients multiples et aux disciplines de service, le théorème d'arrivée et l'analyse par valeurs moyennes pour les réseaux fermés, ainsi que la quasi-réversibilité comme raison structurelle de la forme produit.

Core questions

• Comment les probabilités de routage déterminent-elles le taux d'arrivée effectif à chaque station ?
• Quand la distribution stationnaire conjointe se factorise-t-elle en un produit sur les stations ?
• En quoi les réseaux fermés avec une population de clients fixe diffèrent-ils des réseaux ouverts ?
• Quelle propriété structurelle des stations garantit la forme produit ?

Key theories

Théorème de la forme produit de Jackson

Dans un réseau ouvert de files d'attente exponentielles à serveur unique avec routage markovien, la distribution stationnaire est le produit de distributions géométriques dont les paramètres proviennent de la solution des équations de trafic, de sorte que les stations se comportent comme si elles étaient indépendantes à l'équilibre.

Quasi-réversibilité et le théorème BCMP

Les stations quasi-réversibles se combinent pour former des réseaux avec des équilibres de forme produit, et le théorème BCMP étend cela à plusieurs classes de clients et à plusieurs disciplines de service, élargissant considérablement la classe des réseaux traitables.

Clinical relevance

Les réseaux de files d'attente modélisent les systèmes informatiques, les réseaux de communication et de paquets, la fabrication flexible et les chaînes d'approvisionnement, et la théorie de la forme produit ainsi que l'analyse par valeurs moyennes fournissent des prédictions de performance efficaces concernant le débit, l'utilisation et le temps de réponse sans simuler l'intégralité de l'espace d'états conjoints.

History

Jackson a introduit les réseaux ouverts avec des solutions de forme produit en 1957, Gordon et Newell ont traité les réseaux fermés en 1967, le théorème BCMP de 1975 a unifié les classes et disciplines multiples, et la monographie de Kelly de 1979 a expliqué la forme produit par la réversibilité, établissant la théorie sous-jacente à l'analyse des performances des systèmes informatiques.

Key figures

• James Jackson
• Frank Kelly
• Forest Baskett
• Mani Chandy

Seminal works

• kelly1979
• jackson1957

Frequently asked questions

Qu'est-ce qu'un réseau de forme produit ?

C'est un réseau de files d'attente dont la distribution d'équilibre se factorise en un produit de termes, un par station, de sorte que les stations apparaissent statistiquement indépendantes en régime permanent, même si les clients circulent entre elles.

Quelle est la différence entre les réseaux ouverts et fermés ?

Un réseau ouvert présente des arrivées et des départs externes, de sorte que la population de clients fluctue, tandis qu'un réseau fermé fait circuler un nombre fixe de clients entre les stations sans entrées ni sorties.