SAAFA-76-MRRRCH
Stabilité forte dans un système d’attente MGeo(X)/G/1
Systèmes de files d’attente avec arrivées par groupes
Dans les problemes d’attente, l’interet est centre autour du calcul des mesures de performances (temps d’attente, le nombre de clients dans le système). Plusieurs méthodes (analytiques et approximatives) ont été developpees `a ce sujet. La théorie des files d’attente avec arrivées par groupes prend en compte une spécificité rencontrée dans la pratique. C’est pourquoi elle a fait l’objet de nombreux travaux: [8], [36], [80], [96], [82], L’approximation simple de la probabilité du temps d’attente a été donnée par Eikeboom et Tijms [47] pour des cas particuliers de service exponentiel et déterministe. Dans [100], Van Ommeren a donné deux approximations de la distribution d’attente pour un client arbitraire dans le système MX/G/1. Van Ommeren [99] a étudié le système GIX/G/1. Il a analysé la distribution du temps d’attente d’un client d’un groupe d’arrivés et il a montré sous des conditions appropriées que la distribution du temps d’attente d’un client est asymptotiquement une expansion exponentielle. Chaudhry et Gupta [32], ont donné une méthode approximative pour l’étude de la distribution du temps d’attente du premier client et d’un client arbitraire d’un groupe donné dans le système MX/G/1. Dans [25], Chaudhry et Brière ont réalisé des calculs numériques pour obtenir la distribution du temps de service dans le système MX/G/1. Pour le calcul de la distribution du temps d’attente dans les systèmes avec arrivées par groupes, Baba [10] a fait une analyse analytique pour quelques caractéristiques de plusieurs files. Les methodes exactes pour le calcul de la distribution du temps d’attente dans le système MX/G/1 ont été discutées par Chaudhry et Templeton [35], Neuts [84] et Tijms [95]. Dans [51], Gaver, en utilisant la théorie de renouvellement, a donné la fonction génératrice pour la distribution limite du nombre de clients (dans le système) `a un instant aléatoire du système MX/G/1 . Sahbazov a calculé la fonction génératrice du nombre de clients dans le système aux instants de départ et la distribution du temps d’attente d’un client quelconque en utilisant la technique de la chaine de Markov induite. Dans [34], Agarwal, Chaudhry et Gupta ont calculé la distribution limite du nombre de clients dans le système, pour des files d’attente MX/G/1, avec une méthode basée sur les racines de l’équation caractéristique associé du modèle. Chapitre 1. Systèmes de files d’attente avec arrivées par groupes 8 Le système GeoX/G/1 a été étudié par beaucoup de chercheurs : Dafermos et Neuts [43], Kobayashi [71], Hunter [59], Bruneel et Kim [27], Takagi [93], Chaudhry [31], Tsuchiya et Takahashi [97]et Sanjay Bose [21]. Artalejo et Atencia [57], ont étudié le système MX/G/1 avec rappels. A¨ıssani [3], a étudié le système MX/G/1 avec rappels et serveur non fiable et avec vacances. Le système MX/G1,G2/1 a été étudié par Choudhury [41], Madan et Al.Masri [77], avec deux distributions de service différentes. Dans [72], Konstantin, Ayesta et Brown ont étudié le système MX/G/1 avec processor sharing. Altiok [8], a étudié le modèle MX/G/1 avec une discipline de service exhaustive. Le modèle MX/G/1 `a capacité finie a été étudié par Tijms et Van Ommeren [96]. Dans l’article [67](2007), les auteurs ont considéré un système BMAP/PH/N/0 opérant dans un espace d’états finie. Les Disciplines d’admission partielles et admission complète sont analysées. Ils ont obtenu la distribution stationnaire du système et la probabilité de perte et quelques mesures de performances du système. Ils ont aussi obtenu la transformé de Laplace–Stieltjes de la distribution du temps de séjour des clients. L’article [13](2006), considère un système avec arrivées par groupes Markoviennes `a capacité finie. Les auteurs ont obtenu la distributions de la longueur de la file `a un instant aléatoire et quelques mesures de performance. Ils ont aussi obtenu la transformée de Laplace–Stieltjes du temps d’attente du premier client et d’un client arbitraire. Dans [58], les auteurs ont introduit et analysé un modèle avec arrivées par groupes Markoviennes. Ils ont montré que sous certaines conditions, le processus induit aux instants de départ des clients est de type M/G/1 . Ils ont dérivé des expressions pour le calcul de la distribution du temps d’attente. Dans [103], les auteurs ont développé un ensemble d’équations pour le système BMAP/G/1 et ils ont obtenu la fonction génératrice de la longueur de la file et en se basant sur la forme de la fonction génératrice, ils ont proposé une approche pour le calcul des mesures de performance du système BMAP/G/1 `a temps discret. Un intérˆet majeur est porté `a l’étude des modèles d’attente avec arrivées par groupes et avec vacances. Ces modèles ont été étudiés par Baba [11], Lee et Srinivasan [73], Lee et al [74, 75], Borthakur et Choudhury [20], Choudhury [39, 38], Madan et Al-Rawwah [78], Chapitre 1. Systèmes de files d’attente avec arrivées par groupes 9 Chae et Lee [28], Medhi [81]. Thomo [94], a étudié le système MX/G/1 `a vacances multiples, Il a donné la fonction génératrice du nombre de clients dans le système juste après le départ d’un client et la transformée de Laplace du temps d’attente d’un client. Choudhury [40], a analysé le système MX/G/1 avec vacances multiples. Il a étudié le comportement de la distribution de la longueur de la file aux instants arbitraires et aux instants de départ des clients par une approche analytique. Il a obtenu la fonction génératrice de la longueur de la file aux instants de départ. A¨ıssani [2] a étudié le système MX/G/1 avec rappels et vacations exhaustives, Il a aussi considéré dans [3], le système MX/G/1 avec rappels et serveurs sujets `a des interruptions contrˆolables (vacances) et des interruptions aléatoires (pannes). Dans [64], Kawasaki, Takagi, Hong et Hasegawa ont étudié le système MX/G/1 avec priorité relative et priorité absolu, avec ou sans vacance, avec discipline de service aléatoire. Armero et Conesa (1998) ont fait une analyse statistique pour l’étude des mesures de performances du système MX/M/1 par l’approche Bayesienne. Le point essentiel est dans la prédiction des mesures usuelles des performances du système `a l’équilibre (exp : la distribution predictive `a posteriori du nombre de clients dans le système, la distribution `a posteriori du temps d’attente dans la file et dans le système, du premier client d’un groupe d’arrivées, . . .). Ils ont illustré leurs procédures de calcul par la loi géométrique de la taille des groupes.
Application pratique des systèmes d’attente avec arrivées par groupes
Les systemes de files d’attente avec arrivées par groupes ont été largement appliqués pour la modélisation des performances de plusieurs situations rencontrées en pratique o`u les clients arrivent en groupes de taille aléatoire, tels que les systèmes informatiques, les réseaux de communication, les systèmes de production, les systèmes de transport (trafic maritime et aérien, . . . ). Beaucoup de chercheurs ont modélisé `a l’aide des processus d’arrivées par groupes Markoviens: BMAP (Batch Markovian Arrival Processus) des systèmes réels par une file d’attente BMAP/G/1 `a capacité finie ou infinie o`u les requˆetes arrivent en groupes dans le but d’évaluer : – Loi du nombre de clients en attente, – Loi du temps d’attente, – La probabilité de perte dans le cas d’une capacité finie. Les processus BMAP continus ont été introduit par Lucantoni [76](1991). La version discrète de ce type de processus noté D-BMAP était proposé par Blondia et Casals [17](1992) et ont re¸cu une très grande attention. Les processus D-BMAP appartiennent `a la classe des processus Markoviens additifs. Ils possèdent de bonnes propriétés. L’application des processus avec arrivées par groupes est très large dans le domaine des télécommunications. Prenons par exemple les réseaux IP, o`u les fonctions principales des routeurs consistent `a envoyer les paquets aussi vite que possible ainsi que construire et échanger les informations de routage avec ses voisins. Les routeurs d’accès se chargent des fonctions de contrˆole d’intégrité et d’admission des paquets dans le réseau. Le réseau IP, accepte tout le trafic. Il fonctionne en mode datagramme. Le trafic consiste en une des entités discrètes (les paquets) produites par chaque source. Les processus d’arrivées, généralement utilisés dans ce contexte pour modéliser le trafic, sont des processus d’arrivées par groupes Markoviens : BMAP (Batch Markovian Arrival Processus). Donnons `a présent quelques travaux o`u les phénomènes pratiques ont été modélisés par des systèmes d’attente avec arrivées par groupes avec une distribution générale de la taille des groupes. Chapitre 1. Systèmes de files d’attente avec arrivées par groupes 11 Dans [29] Chakka (2002), a utilisé un système avec arrivées par groupes pour modéliser un routeur et il a donné un calcul efficace des mesures de performances ( ex: taille moyenne de la file, nombre moyen de clients dans le système, . . .) pour les noeuds opérationnels dans les réseaux MPLS. Dans [18], Bonald et Roberts (2003) ont analysé les performances du système de transmission du trafic internet (les pages Web, MP3, e-mails, . . .) avec la taille des groupes géométrique. L’application au réseau ATM a été faite par : He et Sohraby (2001) dans [56] pour la modélisation du ATM multiplexeur (système `a temps discret) par un modèle avec arrivées par groupes GX/D/m. Quand `a Chaudhry et Gupta (2001) dans [33], ils ont appliqué le modèle GIX/G/1 dans les systèmes de télécommunication modernes basés sur ATM et B-ISDN. La modélisation des systèmes `a capacité finie a été élaborée par Tijms et Van Ommeren dans [36](1989) , pour analyser le comportement d’un buffer d’un système de communication informatique par MX/G/1 `a capacité finie. Une application dans les systèmes de traitement parallèle centralisé a été faite par Nelson et al, pour analyser ces performances par un modèle d’attente MX/M/c. Quant `a Zhao et Compbell (1996), ils ont modélisé et analysé les performances du système de transmission par satellite par un modèle d’attente DX/Dm/1. Balay et Nilsson dans [12] (1995 ) ont modélisé le trafic d’un nœud ATM par un processus de Bernoulli avec arrivées par groupes. Ils ont proposé une méthode exact pour l’obtention des mesures de performances. Klemm, Lindmann et Lohman dans [69] proposent une approche de modélisation d’un trafic UMTS (Universal Mobile Telecommunication system). Elle se base sur les mesures du trafic IP. L’idée clè était d’utiliser les processus des arrivées par groupes Markoviennes (BMAP) pour les différentes tailles des paquets IP. Dans [70](2003), ils ont introduit une méthode efficace pour estimer les paramètres du BMAP avec l’algorithme EM (Expansion Maximisation), et pour démontrer l’avantage des BMAPs, il ont fait une étude comparative avec les processus de Poisson. Chapitre 1. Systèmes de files d’attente avec arrivées par groupes 12 Dans l’application de Van der Mai (2000), le serveur représente le serveur Web, les clients représentent les fichiers de demandes individuellement, et chaque fichier de demande est représenté par un groupe de clients. Bruneel[26] (1993) a considéré un processus avec un seul serveur et de capacité infinie avec arrivées par groupes. La distribution du nombre de clients `a chaque arrivées, ainsi que le temps de service de chaque client est une loi générale en utilisant la chaˆıne de Markov induite `a deux dimensions. Les résultats de cet analyse inclus la fonction génératrice du nombre de clients dans le système `a un instant quelconque, le temps d’attente des clients. Les résultats de cette analyse ont été appliqués au phénomène d’attente dans les systèmes de communication. L’article [83] a étudié l’application des processus des arrivées par groupes dans le serveur Web. Les auteurs ont considéré une file d’attente `a infinité de serveurs o`u les clients arrivent en groupes selon un processus de Markov. Les clients commence leurs services immédiatement après leurs arrivées. Ils ont donné la fonction génératrice du nombre de clients dans chaque nœud et le nombre de transitions dans le nœud. En utilisant la loi de Little, ils ont établi les performances du système, illustrés par un exemple numérique appliqué `a un serveur Web. Dans [107](1998), Nui et Takahashi ont modélisé le trafic IP pour le réseau ATM o`u les paquets IP arrivent en groupes par un système de files d’attente `a capacité finie BMAP/G/1/k avec vacances, en utilisant la technique des variables supplémentaires. Ils ont exprimé la probabilité de perte des paquets, le délai moyen des paquets IP, taux d’utilisation des serveur, . . ..
|
Table des matières
Introduction generale
1 Systèmes de files d’attente avec arrivées par groupes
1.1 Introduction
1.2 Systèmes de files d’attente avec arrivées par groupes
1.3 Application pratique des systèmes d’attente avec arrivées par groupes
1.4 Modèle mathématique des systèmes de files d’attente avec arrivées par groupes
1.4.1 Le modèle MX/M/1
1.4.2 Le modèle MX/G/1
1.4.3 Le modèle MGeo(X)/G/1
1.5 Conclusion
2 Approche de stabilité forte
2.1 Théorie de stabilité forte
2.1.1 Critère de stabilité forte
2.2 Inégalités de stabilité forte
2.3 Application aux systèmes de files d’attente
2.3.1 Stabilité forte dans un système MGeo(X)/M/1
2.3.2 Inégalités de stabilité
2.4 Conclusion
3 Stabilité forte dans un système d’attente MGeo(X)/G/1
3.1 Stabilité forte
3.2 Inégalités de Stabilité
3.2.1 Déviation de l’opérateur de transition
3.2.2 Estimation quantitatives
3.3 Conclusion
Table des matières
4 Algorithme et application numérique
Introduction .
4.1 Algorithme STR-STAB-VAC
4.2 Simulation
4.2.1 Modèle de simulation
4.2.2 Validation de la simulation
4.3 Application de l’algorithme ”STR-STAB-GRP”
4.3.1 Application de l’algorithme au système MX/M/1
4.3.2 Discussion des résultats
4.3.3 Application de l’algorithme au cas MX/E2/1
4.3.4 Discussion des résultats
4.4 Conclusion
Conclusion generale
Bibliographie
Télécharger le rapport complet
