Reduced complexity in M/Ph/c/N queues

Alexandre Brandwajn 1 Thomas Begin 2
2 DANTE - Dynamic Networks : Temporal and Structural Capture Approach
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme, IXXI - Institut Rhône-Alpin des systèmes complexes
Résumé : De nombreux systèmes réels peuvent être vus comme des instantiations de la file classique M/G/c/N. La solution analytique exacte de ce modèle file d'attente demeure inconnu, et une approche fréquemment employée consiste à remplacer la distribution générale du temps de service par une distribution de type phase. L'avantage de cette approche est que la file M/Ph/c/N résultante peut être décrite par des équations d'équilibres familières. Le désavantage est que la taille de l'espace d'état résultant souffre du "dimensionality curse", i.e., il croît combinatoirement lorsque le nombre de serveurs et /ou de phases s'accroît. Pour pallier ce problème de complexité, nous proposons d'utiliser, à la place de la description d'état classique complète, une description d'état réduite dans laquelle l'état d'un seul serveur est représenté explicitement, les autres étant pris en compte par leur taux de fins de service. La précision de l'approximation résultante est généralement bonne et, en plus, elle tend à s'améliorer lorsque le nombre de serveurs dans le système s'accroît. Sa complexité de calcul en terme de nombre d'état s'accroît seulement linéairement avec le nombre de serveurs et de phases, ce qui permet la résolution numérique de ce type de files avec des centaines de serveurs et un nombre raisonnable de phases.
Type de document :
Rapport
[Research Report] RR-8303, INRIA. 2013, pp.15
Liste complète des métadonnées

Littérature citée [1 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00821769
Contributeur : Thomas Begin <>
Soumis le : lundi 13 mai 2013 - 00:39:36
Dernière modification le : mardi 16 janvier 2018 - 16:29:46
Document(s) archivé(s) le : mercredi 14 août 2013 - 03:00:10

Fichier

RR-8303.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00821769, version 1

Collections

Citation

Alexandre Brandwajn, Thomas Begin. Reduced complexity in M/Ph/c/N queues. [Research Report] RR-8303, INRIA. 2013, pp.15. 〈hal-00821769〉

Partager

Métriques

Consultations de la notice

297

Téléchargements de fichiers

253