Academic literature on the topic 'Processus de Markovthéorie des files d'attente'

Dans la première partie de cette thèse nous étudions la mobilité et le temps de transfert d'un message dans les réseaux ad hoc mobiles. Nous obtenons, pour plusieurs modèles de mobilité, la loi stationnaire de la position des noeuds, la distribution du temps nécessaire avant que deux noeuds puissent (à nouveau) communiquer, et le temps durant lequel deux noeuds sont dans leur voisinage mutuel. Nous déduisons de ces résultats des formules pour le temps de transfert d'un message en utilisant d'autres noeuds dans le réseau comme relais. Ces calculs sont effectués pour plusieurs modèles de mobilité et pour deux types de protocoles de routage.La deuxième partie de cette thèse traite d'un système à " Polling " qui consiste en deux files d'attente servies par un serveur. Après avoir servi une file d'attente, le serveur a besoin d'un temps de commutation pour passer d'une file à l'autre, et commencer à servir les clients. Les temps de commutation peuvent être corrélés. Nous obtenons l'expression de plusieurs mesures de performance, notamment le temps d'attente moyen et la taille moyenne de la file d'attente. Grâce à ces expressions, nous comparons deux disciplines de service et au travers d'exemples nous montrons que la corrélation des temps de commutation peut augmenter significativement le temps d'attente moyen et la taille des files d'attente. Cela indique que la corrélation ne peut pas être ignorée et qu'elle a des implications importantes pour des systèmes de communication dans lesquels un canal de communication commun est partagé entre plusieurs utilisateurs et où le temps entre des transferts de données consécutifs est corrélé (par exemple dans les réseaux ad hoc).Dans la troisième et dernière partie nous étudions deux files d'attente en série avec des coûts pour chaque client dans le système. La fonction de valeur est calculée pour le coût moyen quand il n'y a pas d'entrée des clients. Celle-ci peut être utilisée pour l'optimisation des systèmes en série ou pour le calcul complet de la fonction de valeur.

On considère une file d'attente fluide dont les taux d'arrivées et de service sont controlés par une chaîne de Markov en temps continu. On étudie les distributions du niveau et de la période d'occupation de la file fluide en régimes transitoire et stationnaire. En régime transitoire, on résoud pour cela un système infini d'équations aux dérivées partielles hyperbolique à coefficients constants. Les solutions sont exprimées sous forme d'une série entière. Le calcul des coefficients associés est très stable et précis. Pour une file fluide pilotée par une file d'attente M/M/1, la convergence des coefficients est établie et permet de réduire le nombre de calcul. En régime stationnaire, différentes solutions sont présentées, généralement basées sur la factorisation de Wiener-Hopf. Dans le cas particulier précédent, la distribution stationnaire du niveau d'occupation de la file fluide est exprimée sous forme d'une série entière dont les coeffficients sont explicitement donnés.

Cette étude se compose de deux parties distinctes qui appréhendent deux aspects différents de la non-stationnarité dans les files d'attente markoviennes. Nous introduisons dans la première partie, deux modèles d files d'attente exponentielles ayant des paramètres non stationnaires dans le temps et n'obéissant pas à l'hypothèse classique d'indépendance. Nous faisons une analyse complète de ces deux modèles (conditions nécessaires et suffisantes de stabilité (via les critères de Jury), courbes de performance et cas particuliers). Une généralisation d chacun de ces deux modèles termine cette première partie. Le premier modèle correspond à une file d’attente (infini ou à capacité limitée avec hystérésis) soumise à un processus d'arrivée de Poisson dont le taux change de façon aléatoire. Le deuxième modèle est une file d'attente avec un serveur pouvant travailler sous deux régimes. A chaque régime correspond un taux de service différent et un contrôle plus ou moins ferme des arrivées. La deuxième partie traite de files d'attente pour lesquels les la loi de service (ou la distribution des arrivées ou les deux) prend sa valeur dans un ensemble dénombrable de distributions générales (Fl. ,. . . ,FN), le passage d'une loi à l'autre étant gouverné par un processus de Markov externe supposé indépendant des lois. Nous étudions trois modèles distincts, le premier correspond à celui décrit c· dessus, le deuxième au "dual" du premier pour la distribution des arrivées et le dernier est une généralisation du premier modèle. De tels systèmes ont été étudiés dans le passé par Yechiali, Naor et Neuts. Nous nous intéressons au cas particulier pour lequel le processus de Markov gouvernant le passage d'une loi à l'autre est supposé quasi-décomposable (au sens défini par Courtois). Dans une première section, nous démontrons formellement que, pour les trois modèles décrits succinctement ci-dessus, la quasi-déco possibilité de ce processus de Markov se reporte sur la fie globale (avec conservation des paramètres). Et finalement, nous donnons une solution approchée pour le premier modèle, en utilisant la notion de fonction génératrice. Dans le cas important des variations lentes entre les différentes lois de service, nous évaluons l'erreur due à l'appr8xima:ion et présentons quelques courbes de performance
This thesis is divided into two distinct parts, each one concerning a different aspect of non-stationary in Markovian queueing systems. In the first part, we introduce two models of exponential queueing systems with non-stationary parameters which do not obey a certain independence assumption often made in Queueing Theory. A complete analysis is carried out (i. E. Explicit results, necessary and sufficient conditions for stability (via Jury's criteria), curves. ). This first part ends with a generalization of those two models. The first model is a queue (infinite or capacity limited with a resume level), whose arrival process is Poisson with a randomly changing arrival rate. The second model is a queue with randomly changing service rate. The second part deals with queueing systems whose service process (or arrival process, or both) takes its value from a finite set of general distributions (Fl,. . . ,FN). The passage from one distribution to another is governed by a extraneous Markov process which is assumed to be independent of the distributions. We study three distinct models, the first one corresponding to the one described above, the second is the "dual" of the first one for the arrival process and the third one is a generalization of the first one. These systems have already been studied by Yechiali, Naor and Neuts. In this second part, we deal with the particular case where the extraneous Markov process is quasi-decomposable (as defined by Courtois). We first show, formally, that these three models are quasi­ decomposable with the same parameter as for the extranecus Markov process. Finally, we give an approximate solution for the first model, using z-transforms. In the very important case of slow variations between the different service distributions, we compute the error due to the approximation and present performance curves

Le développement du temps-réel est aujourd'hui une préoccupation majeure dans la conception des réseaux de télécommunication et des réseaux informatiques. Toute donnée doit alors avoir une "durée de vie" très limitée dans le système, puisque son traitement doit être instantané. Pour rendre compte de cette contrainte dans la représentation d'un nœud du réseau, on enrichit le modèle classique de la file d'attente d'un nouveau paramètre: le délai d'exécution des tâches. On parlera donc de file d'attente avec clients impatients: ils entrent dans le magasin avec une patience limitée et le quittent si leur délai expire avant d'avoir atteint un serveur. Nous étudions des cas où la discipline de service dépend du délai des clients ( EDF: on sert le plus pressé, LDF: le moins pressé...). Ceux-ci présentent une dynamique instable, ce qui en complique notoirement la description markovienne. Pour un système général sous toute discipline de service, un schéma de récurrence arrière aux instants de fins de service nous permet de prouver sous Palm l'Existence/Unicité du régime stationnaire, et de donner la condition de récurrence. Nous prouvons dans le même cadre par des techniques de couplage qu'EDF est la discipline optimale et que LDF est la pire pour la probabilité de perte à l'équilibre P et donnons une borne du gain d'EDF en terme de P. Nous calculons en outre des encadrements de P sous EDF dans certains cas. Nous proposons ensuite une description markovienne de la file d'attente avec clients impatients par le processus à valeur mesures ponctuelles simples où chaque masse de Dirac représente le délai résiduel d'un client en attente ou déjà perdu. Nous donnons la limite fluide d'une suite de renormalisations de ce processus en espace, temps et amplitude, ainsi qu'un théorème central limite fonctionnel établissant la convergence en loi de l'écart à la limite vers un processus de diffusion . La limite fluide, à trajectoires continues et déterministes, s'écrit explicitement comme l'unique solution d'une équation intégrale dans l'espace des processus à valeurs distributions tempérées. Les convergences s'obtiennent par passage aux fonctions tests du dual, et par des méthodes de compacité/unicité. Nous appliquons ces résultats à l'estimation asymptotique des processus de congestion et de perte sous EDF et FIFO, et au système délai pur.

Le domaine étudié est celui de la stabilité du trafic et du stockage de messages dans les réseaux informatiques. On rappelle les principaux résultats sur les fonctions de Liapunov. La suite du premier chapitre est consacrée aux limites fluides, méthode développée depuis les années 90. Elles ont l'avantage de décrire un modèle sous une forme macroscopique et permettent ainsi d'écrire de façon simplifiée les équations régies par la dynamique établie sur le réseau. Une condition de stabilité est établie à partir du modèle fluide. On étudie deux modèles de réseaux dont les serveurs tombent en panne de façon aléatoire. Les conditions de stabilité ainsi qu'une convergence de mesures invariantes sont obtenues à l'aide des fonctions de Liapunov. L'anneau de Cambridge, un modèle de réseau local, est étudié sous des hypothèses presque générales. Les serveurs sont repartis à l'intérieur d'un anneau tournant toujours dans le même sens. Les files d'attente sont disposées régulièrement autour de l'anneau. On décrit le modèle fluide et un système d'équations régi par celui-ci. Il permet de trouver les conditions de stabilité de l'anneau. Le modèle suivant est dérive de celui de l'anneau de cambridge. Son but est d'analyser les différents comportements d'un anneau de Cambridge stable, d'un état initial jusqu'a son retour a l'équilibre. On sature certaines files d'attente de façon permanente. Le modèle fluide permet de donner une condition suffisante de stabilité. La dernière application est un modèle simplifie de partage de bande passante. L'étude du modèle fluide apparaît beaucoup plus délicate que pour les modèles précédents. Dans un cas particulier, on établit les conditions de stabilité. La description détaillée du comportement du modèle transient, permet d'obtenir des limites fluides non déterministes.

Face à des systèmes de file d’attente, les clients prennent des décisions stratégiques afin de rejoindre ou non ces systèmes d’une manière optimale. Un nouvel aspect intéressant est apparu et étudié ces dernières années : l’impact de l’information de la longueur de la file sur les décisions stratégiques des clients, sur l’équilibre et les performances du système. Les clients ne sont pas tous semblables face aux informations fournies par le système et cette hétérogénéité impacte également les équilibres et performances. Dans certains cas, le fournisseur de service peut avoir un intérêt à divulguer l’information sur l’état du système à certains clientset même de la cacher à d’autres afin d’optimiser certains objectifs. Dans d’autres cas, l’obtention de l’information est déterminée stratégiquement par les clients qui décident alors de l’inspecter ou non selon leurs contraintes et leurs souhaits. La motivation principale de cette thèse est d’étudier l’impact de l’information dans des systèmes d’attente avec usagers stratégiques et information contrôlée. Nos contributions permettent de déterminer l’équilibre et d’optimiser les performances des systèmes en fonction de l’accessibilité de l’information. Des solutions théoriques et analytiques ont été proposées pour résoudre les problèmes étudiés
Faced to queuing systems, customers can make their strategic decisions in order to join or not these systems. An interesting new aspect has emerged and studied in recent years, which is about the impact of current queue-length information on strategic decisions of customers, on the equilibrium and the performance of the system. Customers are not necessarily homogeneous in their behavior and their access to the information, which implies different equilibrium and performances solutions.In some cases, service provider may have an interest to give to customers the system state information and withholding it to others in order to optimize certain objectives. In other cases, obtaining the information is mainly the choice of customers and therefore thay have to decide to inspect or to collect the information or not, according to their constrainsts and their wishes.The main motivation for this thesis is to study the impact of the queue length information on the strategic decisions of customers and to analyze the performance of such strategic queuing systems with controlled information. Our contributions allow to determine the equilibuim and optimize the performance of the systems according to the queue length information. Theoretical and analytical solutions have been proposed to solve the studied problems

Cette thèse présente du travail dans le cadre de la modélisation et de la vérification de systèmes de processus asynchrones communiquant par files fifo. Un problème majeur pour la vérification est que les files peuvent croître de manière non bornée. Nous proposons une technique d'analyse statique pour réduire la taille des modèles de tels systèmes en "éliminant" certaines files, et ceci tout en préservant certaines propriétés du système. Par "élimination" d'une file nous entendons une consommation au plus tôt des messages posés dans cette file, sans entrelacement avec d'autres actions possibles du systèmes. La justification de cette réduction est basée sur les mêmes arguments des techniques de "réduction d'ordres partiels". Nous définissons une notion de "conflit" sur le graphe de communication d'un système qui sont les cycles de communication et l'existence de plusieurs chemins de communication entre deux nœuds. En absence de conflit, toutes les files peuvent être éliminées. Nous utilisons la méthode d'analyse statique de "slicing" pour raffiner le graphe de communication et éventuellement éliminer certains conflits. Nous montrons qu'il est suffisant de préserver une seule file sur chaque chemin conflictuel. Nous avons implémenté une partie des algorithmes dans l'outil IF développé au laboratoire et appliqué notre méthode à un nombre d'exemples. Dans certains cas, il est possible de rendre finis des systèmes initialement infinis.

On introduit un nouveau modèle de file d'attente: les files Zéro-automatiques. Tout d'abord, on considère la discipline de service Premier Arrivé Premier Servi. Les files 0-automatiques sont caractérisé par une salle d'attente évoluant suivant un mécanisme de marche aléatoire sur un groupe ou un monoïde infini. En considérant les deux cas les plus simples et aussi extrêmes des files 0-automatique, nous récupérons la file simple M/M/1, et la G-file de Gelenbe avec les clients positifs et négatifs. Le résultat saillant est que toutes les files 0-automatiques ont une distribution stationnaire à forme produit et un processus de départ Poisson. Il est un point crucial pour construire les réseaux de files 0-automatiques dont les distributions stationnaires à forme produit. On considère deux modèles correspondant aux différents routages classiques: réseau à la Jackson et réseau à la Kelly. Dans les deux cas, on a montré que la distribution stationnaire a une distribution stationnaire à forme produit et peut être déterminée explicite. De plus, le processus de départ est Poisson. Considérons les files 0-automatiques avec discipline de service Dernier Arrivé Premier Servi, quelques propriétés ne sont plus vraies. Cependant, il est intéressant de comparer deux types de files
We introduce and study a new model: Zero-automatic queues. First, we consider the discipline First In First Out. Roughly, 0-automatic queues are characterized by a special buffering mechanism evolving like a random walk on some infinite group or monoid. When considering the two simplest and extremal cases of 0-automatic queues, we recover the simple M/M/1 queue, and Gelenbe's G-queue with positive and negative customers. The salient result is that all stable 0-automatic queues have a product form stationary distribution and a Poisson output process. This is a crucial point to build a network of 0-automatic queues with product form stationary distribution. We consider two types of networks, with either a Jackson-like or a Kelly-like touting mechanism. In both cases, and under the stability condition, we prove that the stationary distribution of the buffer contents has a « product-form » and can be explicitly determined. Furthermore, the departure process out of the network is Poisson. Consider the 0-automatic queues with the service discipline Last In First Out, ail nice properties of the FIFO 0-automatic queues do not hold for the LIFO queue. However, it is intersting to compare these two types of queues

Présentation des outils d'analyse pour les réseaux a files (réseaux à files à choix libre topologique et réseaux linéaires). Utilisation du réseau coloré associé permettant de décider la quasi-vivacité, la terminaison infinie et la vivacité. Détermination du centre des réseaux. Forme générale du langage d'entrée des files. Description du langage d'un système de deux processus communiquant par files (langage d'un réseau de Pétri)

Cette thèse est consacrée à l'étude des réseaux de Bramson et leurs modèles fluides associés. Ces réseaux font partie de le famille des réseaux de files d'attente à plusieurs classes de clients. Une de leurs propriétés fondamentales est qu'ils peuvent être instables même quand la charge moyenne de travail qui arrive à chaque file est strictement plus petite que sa capacité. Dans le premier chapitre nous rappelons les notions de réseaux multi-classes, celles des limites fluides et le lien entre stabilité fluide et stabilité stochastique. L'analyse des modèles fluides associés au réseau de Bramson avec un seul rebouclage est faite dans le deuxième chapitre. On démontre, sous certaines hypothèses sur les taux de service, la stabilité du réseau. Dans le troisième chapitre nous montrons que le réseau de Bramson fluide avec deux rebouclages peut être instable quand le premier service à la station 1 et les deuxième et troisième services à la station 2 sont nuls. La démonstration est basée sur la notion de couches homogènes, définie par Bramson et Dumas, et sur celle de cycles d'instabilité. Le quatrième chapitre porte sur l'extension du résultat du chapitre trois au cas où toutes les durées de service sont de moyennes non nulles. La notion de couche homogène est généralisée. Alors les taux de départ des diverses classes de clients sont encadrés par des constantes strictement positives.

Ce chapitre étudie les conditions de stabilité pour un système de file d'attente multiserveur avec des serveurs hétérogènes et un flux d'entrée régénératif X. L'idée principale est de construire un processus de service auxiliaire Y ainsi que la détermination des points communs de régénération pour les deux processus X et Y. Les possibilités de l'approche proposée sont illustrées par des exemples. Nous présentons également les applications à l'analyse de capacité des systèmes de transport.

Dans ce chapitre, nous abordons les distributions de probabilités et les processus aléatoires liés aux modèles de file d'attente et de fiabilité incorporés dans un environnement périodique. L'analyse de ces distributions nous aide à comprendre leur structure et à étendre le champ de leurs applications et leur pouvoir de modélisation. Nous voyons comment elles peuvent être utilisées pour modéliser divers processus en économie, en études actuarielles, dans l'industrie, la démographie, les études environnementales, et comment leur utilisation se répercute sur l'assurance, l'analyse des risques et des coûts. Ce chapitre est conçu pour donner des incitations, des compétences analytiques et de l’inspiration aux étudiants et aux chercheurs. De nouvelles orientations sont marquées. Les approches, les méthodes et les résultats donnent une base pour de multiples études et applications ultérieures.