Dissertations / Theses: 'Processus de Markovthéorie des files d'attente'

1

Groenevelt, Robin. "Modèles stochastiques pour les réseaux ad hoc mobiles." Phd thesis, Université de Nice Sophia-Antipolis, 2005. http://tel.archives-ouvertes.fr/tel-00274901.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

2

Barbot, Nelly. "Files d'attente fluides en environnement markovien." Rennes 1, 2002. http://www.theses.fr/2002REN10094.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

3

Rosenberg, Catherine. "Non-stationnarité dans les files d'attente markoviennes." Paris 11, 1986. http://www.theses.fr/1986PA112242.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

4

Moyal, Pascal. "Contributions à l'étude des files d'attente avec clients impatients." Phd thesis, Télécom ParisTech, 2005. http://pastel.archives-ouvertes.fr/pastel-00001340.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

5

Dantzer, Jean-François. "Stabilité des réseaux de files d'attente et limites fluides stochastiques." Versailles-St Quentin en Yvelines, 2000. http://www.theses.fr/2000VERS0010.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

6

Naceur, Tesnim. "Systèmes de files d'attente stratégiques avec information contrôlée." Thesis, Avignon, 2020. http://www.theses.fr/2020AVIG0279.

Full text

Abstract:

Face à des systèmes de ﬁle d’attente, les clients prennent des décisions stratégiques aﬁn 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 ﬁle 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 aﬁn 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

APA, Harvard, Vancouver, ISO, and other styles

7

Aguilar, Cornejo Manuel. "Contribution à la validation de systèmes de processus communiquant par files d'attente : analyse statique pour la réduction de files." Grenoble INPG, 2003. http://www.theses.fr/2003INPG0106.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

8

Dao, Thi Thu Ha. "Les files et les réseaux zéro-automatiques." Paris 7, 2007. http://www.theses.fr/2007PA077141.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

9

Choquet-Geniet, Annie. "Analyse et propriétés des processus communiquant par files fifo : réseaux à files à choix libre topologique et réseaux à files linéaires." Paris 11, 1987. http://www.theses.fr/1987PA112248.

Full text

Abstract:

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)

APA, Harvard, Vancouver, ISO, and other styles

10

El, Merzouqi Saïd. "Stabilité et instabilité des réseaux de files d'attente stochastiques à plusieurs classes de clients." Rouen, 2002. http://www.theses.fr/2002ROUES044.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

11

Arrar, Nawel Khadidja. "Problèmes de convergence, optimisation d'algorithmes et analyse stochastique de systèmes de files d'attente avec rappels." Paris 1, 2012. http://www.theses.fr/2012PA010067.

Full text

Abstract:

Pour optimiser la gestion des réseaux de télécommunication, nous considérons le système de file d'attente MX/G/1 avec rappels et clients impatients. En utilisant la méthode des variables supplémentaires, nous obtenons les fonctions génératrices partielles de l'état stationnaire conjointe de l'état du serveur et du nombre de clients dans le groupe de rappels. Pour compléter l'analyse du modèle considéré, nous calculons la distribution stationnaire de la chaîne de Markov induite, grâce à laquelle nous présentons la propriété de la décomposition stochastique. Cependant, la fonction génératrice de la distribution stationnaire du nombre de clients dans le groupe de rappels, est obtenue sous une forme explicite, très complexe et ne révèle pas la nature de la distribution en question. Alors, nous étudions le comportement asymptotique de la variable aléatoire représentant le nombre de clients en orbite et dans le système pour des valeurs limites des différents paramètres. Nous complétons notre travail par des exemples numériques.

APA, Harvard, Vancouver, ISO, and other styles

12

Charlot, François. "Systèmes de files d'attente : stabilité, récurrence, convergence en loi et intégrabilité." Rouen, 1988. http://www.theses.fr/1988ROUES033.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Massoulié, Laurent. "Stabilite, simulation et optimisation des systemes a evenements discrets." Paris 11, 1995. http://www.theses.fr/1995PA112172.

Full text

Abstract:

Ce travail traite des systemes stochastiques dynamiques a evenements discrets, ou systemes entraines par des processus ponctuels. La premiere partie est consacree a l'etude qualitative de ces systemes, et plus precisement a leurs proprietes de stabilite. Ici, on entend par stabilite l'existence d'un unique regime stationnaire, et la convergence vers cet etat stationnaire pour une classe de conditions initiales. Premierement, on etablit plusieurs resultats de stabilite pour une categorie de processus ponctuels en interaction. Ces processus decrivent d'une part certains reseaux de files d'attente, et modelisent d'autre part le comportement des reseaux de neurones. Deuxiemement, la stabilite des reseaux de files d'attente dits de polling est demontree sous des hypotheses minimales d'ergodicite sur les processus d'entree dans le systeme. Sous ces memes hypotheses minimales, on montre la stabilite d'un modele d'atelier de production. Dans une deuxieme partie, on se consacre a l'optimisation des prformances de ce systeme de production. Pour cela, on calcule au moyen d'une technique d'analyse de perturbations des estimateurs du gradient des indices de performance du systeme. L'obtention de tels estimateurs est possible car l'information contenue dans les trajectoires des systemes a evenements discrets est tres redondante: ceci est l'idee de base de l'analyse de perturbations. Enfin, ces estimateurs sont utilises dans des algorithmes adaptatifs du type gradient stochastique pour la recherche en temps reel du mode de fonctionnement optimal du systeme

APA, Harvard, Vancouver, ISO, and other styles

14

Dube, Parijat. "Evaluation des performances des phénomènes de congestion dans les réseaux de communication." Nice, 2002. http://www.theses.fr/2002NICE5747.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Harb, Ali. "Faisabilité. Méthodes non standard pour la stabilité des réseaux de files d'attente. GI/GI/q + G." Rouen, 1998. http://www.theses.fr/1998ROUES075.

Full text

Abstract:

Cette thèse est subdivisée en trois parties. Faisabilité : dans cette partie, nous étudions la faisabilité de n flux déterministes d'arrivées dans une file d'attente soumise à la contrainte temps-réel forte. Cette contrainte spécifie que les clients ont un délai maximum sur le temps de séjour dans la file, le client est rejeté dès que le délai maximum est échu. Pour différentes disciplines de service, nous étudions les conditions sous lesquelles la contrainte temps-réel forte est respectée. Réseau de Jackson : ce chapitre traite les réseaux de Jackson sous l'angle de l'analyse non standard. Nous analysons dans cette partie des conditions non habituelles pour la stabilité des réseaux de files d'attente. GI/GI/q + G : cette dernière partie est consacrée à l'étude de la chaîne de Markov associée à la file GI/GI/q + G : on retrouve ici le cadre de la première partie où les clients ont un temps d'impatience qui limite leurs temps de séjour dans la file. Nous démontrons l'irréductibilité et la récurrence au sens de Harris de la chaîne concernée.

APA, Harvard, Vancouver, ISO, and other styles

16

Chedom, Fotso Donatien. "Contributions a l’étude des processus de Markov à temps continu et applications aux théories des files d’attente et de la ruine." Pau, 2010. http://www.theses.fr/2010PAUU3039.

Full text

Abstract:

Dans cette thèse nous nous intéressons à des problèmes pratiques relevant des domaines des files d’attente et du risque qui débouchent sur des modélisations markoviennes dont la résolution exacte et même asymptotique est considérablement difficile. Nous proposons des solutions analytiques qui font usage de deux approches : le numérique (avec deux contributions à la théorie des files d’attente) et le symbolique-numérique (avec une contribution à la théorie des files d’attente et une contribution à la théorie de la ruine)
This thesis deals with practical problems in the areas of queuing and risk that lead to Markov models whose exact or even asymptotic resolution is considerably difficult. We provide analytical solutions which use two approaches : the numeric (with two contributions to queueing theory) and the symbolic-numeric (with a contribution to queueing theory and a contribution to ruin theory)

APA, Harvard, Vancouver, ISO, and other styles

17

Dao, Thi Thu Ha. "Les files et les reseaux zero-automatiques." Phd thesis, Université Paris-Diderot - Paris VII, 2007. http://tel.archives-ouvertes.fr/tel-00195119.

Full text

Abstract:

On introduit un nouveau modele de file d'attente: les files Zero-automatiques. Tout d'abord, on considere la discipline de service Premier Arrive Premier Servi. Les files 0-automatiques sont caracterisees par une salle d'attente evoluant suivant un mecanisme de marche aleatoire sur un groupe ou un monoede infini. En considerant les deux cas les plus simples et aussi extremes de files 0-automatiques, nous retrouvons la file simple M/M/1 et la G-file de Gelenbe avec clients positifs et negatifs.
Le resultat saillant est que toutes les files 0-automatiques ont une distribution stationnaire a forme produit et un processus de depart de Poisson. C'est un point crucial pour construire les reseaux a forme produit.
On considere deux modeles correspondant aux differents routages classiques: reseaux a la Jackson et reseaux a la Kelly. Dans les deux cas, on a montre que la distribution stationnaire est a forme produit et peut etre determinee explicitement. De plus, le processus de depart est Poisson.
Enfin, considerons les files 0-automatiques avec discipline de service Dernier Arrive Premier Servi. Dans ce cas, certaines proprietes restent vraies, mais pas toutes. On obtient des resultats interessants en comparant les zones de stabilite d'une meme file 0-automatique sous les discpilines Premier Arrive Premier Servi et Dernier Arrive Premier Servi.

APA, Harvard, Vancouver, ISO, and other styles

18

Draief, Moez. "Grand réseaux aléatoires : Comportement asymptotique et points fixes." Paris 7, 2005. http://www.theses.fr/2005PA077201.

Full text

Abstract:

Le théorème de Burke est un résultat classique en théorie des files d'attente. Il établit que le processus de départ d'une file M/M/1 est un processus de Poisson de même intensité que le processus des arrivées. Nous présentons des extensions de ce résultat à la file d'attente et au modèle de stockage. Nous abordons ensuite l'étude de ces systèmes en tandem et en régime transitoire. Nous prouvons que les équations qui régissent la dynamique des deux systèmes (file d'attente et modèle de stockage) sont les mêmes alors que les variables pertinentes sont différentes selon le modèle qui nous intéresse. En utilisant des analogies entre ces systèmes et l'algorithme de Robinson-Schensted-Knuth, nous donnons une preuve élégante de la propriété de symétrie de chacun des deux systèmes. Nous nous intéressons également aux corrélations entre les services des clients successifs au sein d'une période d'activité. Nous revenons par la suite au théorème de Burke que l'on peut voir comme étant un résultat de point fixe: le processus de Poisson est un point fixe pour la file d'attente avec des lois de service exponentielles. Nous prouvons des résultats de points fixes dans le cadre des grandes déviations où les variables d'entrée sont décrites par le biais de leurs fonctions de taux
A cornerstone result in queueing theory due to Burke states that the departure process from a stationary M/M/1 queue is a Poisson process having the same intensity as the arrival process. I proved different extensions of this theorem to the single server queue and to the storage model. Furthermore, I looked at these models in tandem in the {\em transient régime}. I showed that these models are dual in a strong fashion. Indeed I proved that the equations governing the dynamics of both models (queue and store) are the same even though the interesting variables are different whether we are interested in the queueing model or in the storage model. I use this duality to give an elegant proof, using analogies with the Robinson-Schensted-Knuth algorithm, of the property of symmetry of both Systems. Moreover I explored the correlations between the laws of the services of successive customers belonging to the same busy period. Burke's theorem can be seen as a fixed point result the Poisson process is a fixed point for the queue with exponential service times. I explored fixed points for the single server queue and the storage model in the context of large deviations where the arrivals and the services are described by means of their rate functions

APA, Harvard, Vancouver, ISO, and other styles

19

Regnault, Philippe. "Différents problèmes liés à l'estimation de l'entropie de Shannon d'une loi, d'un processus de Markov." Phd thesis, Université de Caen, 2011. http://tel.archives-ouvertes.fr/tel-00673694.

Full text

Abstract:

On étudie à la fois l'estimation de l'entropie de Shannon d'une probabilité à partir d'observations indépendantes ou markoviennes, et l'estimation du taux d'entropie d'un processus markovien de sauts d'espace d'état fini, à partir d'observations continues ou discrètes. Plusieurs problèmes connexes sont traités. Certains apparaissent en amont de l'estimation, comme l'étude de la géométrie de la divergence de Kullback-Leibler en lien avec la transformation escorte. D'autres apparaissent comme des applications des résultats d'estimation obtenus. On construit ainsi des tests sur le niveau d'entropie d'une probabilité, à partir d'un principe de grandes déviations pour la suite des estimateurs empiriques de l'entropie d'une suite de variables indépendantes. On étudie également diverses propriétés en lien avec l'estimation de l'entropie et du taux d'entropie de files d'attente modélisées par des processus markoviens de naissance et de mort.

APA, Harvard, Vancouver, ISO, and other styles

20

Ben, Mamoun Mouad. "Encadrements stochastiques et évaluation de performances des réseaux." Versailles-St Quentin en Yvelines, 2002. http://www.theses.fr/2002VERS0012.

Full text

Abstract:

Cette thèse porte sur l'utilisation des techniques de comparaison stochastique pour l'évaluation de performances des systèmes complexes. Ces techniques constituent à construire des modèles plus simples qui fournissent des bornes sur la distribution de probabilité de l'indice de performance considéré. Nous avons considéré cette approche pour l'analyse des systèmes modélisés par des chaînes de Markov. Dans ce cadre, nous avons défini une classe particulière de matrices de transition de chînes de Markov qui ont des propriétés très intéressantes, dont une forme close pour le calcul de la distribution stationnaire. Nous avons ensuite fourni des algorithmes qui permettent de construire des matrices appartenant à cette classe, qui sont bornantes et monotones selon différents ordres stochastiques. Les distributions stationnaires des matrices construites peuvent être calculées à travers la forme close et elles constituent des bornes sur les distributions stationnaires des matrices initiales. Dans ce travail, nous avons porté un intérêt particulier aux ordres stochastiques de variabilité qui fournissent des bornes plus précises que les bornes au sens de l'ordre fort[\preceq]st, habituellement utilisé. Nous avons aussi utilisé l'approche d'encadrements stochastiques pour l'analyse des délais des disciplines de services équitables "Fair Queueing" (FQ) dont la dynamique est très complexe. Nous avons proposé des disciplines bornantes de type "Weighted Round Robin" qui sont plus simples à analyser. En fait, ces disciplines ont un comportement périodique. Ceci nous a permis de faire une analyse Markovienne et fournir des bornes sur les distributions de délais des disciplines FQ. La comparaison des délais est établie au sens de l'ordre trajectoriel [\preceq]st.

APA, Harvard, Vancouver, ISO, and other styles

21

Abu, Amsha Oula. "Application des méthodes de la comparaison stochastique pour l'analyse des disciplines fair queueing." Versailles-St Quentin en Yvelines, 1998. http://www.theses.fr/1998VERS0012.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Kloul, Leïla. "Méthodes d'évaluation des performances pour les réseaux ATM." Versailles-St Quentin en Yvelines, 1996. http://www.theses.fr/1996VERS0001.

Full text

Abstract:

L'analyse quantitative des systèmes parallèles et des protocoles se heurte en générale à l'explosion combinatoire du nombre d'états de ces systèmes. Cette thèse s'intègre dans le contexte de la recherche de solutions analytiques pour les problèmes de dimensionnement des réseaux ATM Trois approches différentes, mais complémentaires, sont proposées: une méthode exacte: La solution a forme produit, Une méthode structurelle: Les réseaux d'automates stochastiques, t, une méthode d'approximation faisant appel aux processus de diffusion. La première approche se situe dans le cadre de la théorie des réseaux de files d'attente avec des clients négatifs ou g-réseaux. Deux extensions des g-réseaux sont prouvées à forme produit. La première consiste à considérer des réseaux ou le taux de service dépend du nombre de clients dans la file et la seconde consiste à considérer des clients négatifs dont le rôle est de détruire tous les clients positifs présents ont leur arrivée dans une file d'attente. Dans chacun des deux cas, un algorithme itératif de calcul de la solution du système de points fixes est propose. La seconde approche est basée sur les réseaux d'automates stochastiques (ras). Cette méthode est utilisée pour modéliser un mécanisme de contrôle de congestion visant à offrir une priorité d'accès aux cellules sensibles d'un réseau ATM. La troisième et dernière approche est l'approximation par diffusion. Les principes théoriques de cette technique sont appliqués à l'analyse des délais de transmission de bout en bout et du phénomène de gigue qui résulte de leur caractère aléatoire. L'étude de la gigue permet de dimensionner le dispositif de rattrapage de gigue et d'en estimer la qualité de service. L'intérêt de l'utilisation de la méthode de l'approximation par diffusion est également mis en évidence au travers d'une seconde étude. Celle-ci concerne l'analyse d'un multiplexeur statistique à intégration de service.

APA, Harvard, Vancouver, ISO, and other styles

23

Combes, Richard. "Mécanismes auto-organisants dans les réseaux sans fil." Paris 6, 2013. http://www.theses.fr/2013PA066028.

Full text

Abstract:

Dans cette thèse on étudie la mise au point, la modélisation et la performance de mécanismes (dits auto-organisants) pour gérer les réseaux sans fils de façon autonome. Le contexte technologique est rappelé, et les outils mathématiques nécessaires sont introduits succinctement: théorie des files d'attente, processus ponctuels, théorie de l'information, approximation stochastique, processus de décision markoviens et apprentissage par renforcement. Dans une première partie, on s'intéresse à l'évaluation de performance des ordonnanceurs opportunistes, et à leur utilisation pour l'optimisation capacité/couverture. Les phénomènes de la couche physique tels que l'évanouissement rapide du canal, les interférences, la structure du récepteur et les schémas de modulation et codage pratiques sont pris en compte. Dans la deuxième partie, un mécanisme d'équilibrage de charge automatique prenant en compte les arrivées et départs des utilisateurs est présenté. Pour un trafic stationnaire, sa convergence vers l'optimum est prouvée par une technique d'approximation stochastique. Pour un trafic non stationnaire, des expériences numériques suggèrent que la méthode est capable de s'adapter aux variations de trafic journalières. Dans une troisième partie, on s'intéresse aux réseaux avec relais. Une formule analytique simple basée sur la théorie des files d'attentes est proposée pour leur dimensionnement. La formule est valable pour le modèle de trafic le plus général (stationnaire ergodique). Le mécanisme d'équilibrage de charge est étendu pour prendre en compte les relais. Une méthode d'équilibrage de charge dynamique utilisant l'apprentissage par renforcement est étudiée
In this thesis we study the design, modeling and performance evaluation of mechanisms which can manage wireless networks autonomously (self-organizing mechanisms). We recall the technological context, and the required mathematical tools are introduced concisely: queuing theory, point processes, information theory, stochastic approximation, Markov decisions processes and reinforcement learning. In the first part, we study opportunistic scheduling. We are interested in their performance evaluation and their use to perform coverage-capacity optimization. Physical layer phenomena such as channel fading, interference, receiver structure and practical modulation and coding schemes are taken into account. In the second part, an algorithm for automatic load balancing is presented. The dynamical arrivals and departures of users are taken into account. For stationary traffic, the convergence of the mechanism to the optimal configuration is shown using stochastic approximation theorems. For non-stationary traffic, numerical experiments suggest that the mechanism is able to adapt itself to daily traffic patterns. In the third part, we study relay-enhanced networks. Based on a queuing analysis, a simple formula for network dimensioning is given. It is valid for the most general traffic model (stationary ergodic input). The load balancing mechanism is extended to relay-enhanced networks. A dynamical load balancing algorithm based on reinforcement is studied

APA, Harvard, Vancouver, ISO, and other styles

24

Peng, Jing. "Modèles de files d’attente pour l'analyse des stratégies de collaboration dans les systèmes de services." Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLC089/document.

Full text

Abstract:

Au cours des vingt dernières années, le secteur des services est devenu le secteur le plus important en nombre d'actifs occupés dans l’économie mondiale, en particulier dans les pays développés. Par ailleurs, la concurrence et la coopération dans le secteur des services sont devenues de plus en plus populaires dans le contexte de la mondialisation économique. Comment collaborer avec un accord gagnant-gagnant apporte une source fertile de problèmes de management des opérations dans le domaine des services. Dans cette thèse, nous étudions des stratégies de collaboration dans des systèmes de services homogènes. Nous nous concentrons en particulier sur les stratégies de pooling des ressources de service.Dans les deux premières parties, nous étudions le problème de partage des coûts entre les fournisseurs de services indépendants avec des temps de service qui suivent une distribution générale et en tenant compte de l'abandon des clients. Nous modélisons à la fois chaque fournisseur de services et la coalition coopérative comme des files d'attente avec serveur unique, et spécialisons les stratégies de pooling avec les capacités de services fixes et modifiables. Dans la dernière partie, nous abordons le problème de pooling dans le cadre multiserveur pour évaluer la qualité de l'hypothèse "superserveur". Nous étudions numériquement l'impact de la variabilité de la durée de service et l'abandon des clients sur les jeux de mise en commun des ressources. Nous comparons aussi les partages des coûts entre le système de "super-serveur" et multiserveur
In past twenty years, the service sector has emerged as the primary sector in the world economy, especially in developed countries. Competition and cooperation in service industries have become more and more popular in the context of economic globalization. How to operate the collaboration with a win-win agreement brings a fertile source of operations management issues in service science. In this thesis, we study collaborations between homogeneous service systems in terms of resource pooling strategies.In the first two parts, we investigate the cost-sharing problem among independent service providers with general service times and accounting for the customer abandonment. We model both the service provider and the cooperative coalition as single server queues, and specialize the capacity pooling strategies with the fixed and optimized service capacities.Finally, we address the service pooling problem in the multi-serverpooling setting to assess the quality of the "super-server" assumption.We numerically investigate the impact of service duration variability and customer abandonment on the pooling game. We compare between cost-sharing results of the two resource pooling concepts, with or without the "super-server" assumptions

APA, Harvard, Vancouver, ISO, and other styles

25

Monteiro, Julian Geraldes. "Modeling and analysis of reliable peer-to-peer storage systems." Nice, 2010. http://www.theses.fr/2010NICE4038.

Full text

Abstract:

Cette thèse vise à fournir des outils permettant d’analyser et de prédire la performance de systèmes de stockage de données à grande échelle. Nous avons utilisé ces outils pour analyser l’impact de différents choix de conception du système sur différentes mesures de performance. Par exemple, la consommation de bande passante, l’espace de stockage et la probabilité de perdre des données doivent être aussi faibles que possible. Tout d’abord, nous décrivons un modèle simple par chaîne de Markov et nous établissons des formules mathématiques closes. Ces formules nous permettent de comprendre les interactions entre les paramètres du système. Nous confirmons en comparant à des simulations que ces modèles donnent des approximations correctes du comportement moyen du système. En effet, un mécanisme de réparation paresseux est étudié et nous décrivons comment régler les paramètres du système pour obtenir une utilisation efficace de la bande passante. Nous proposons ensuite un nouveau modèle stochastique basé sur une approximation fluide pour saisir les écarts par rapport au comportement moyen. De plus, nous étudions plusieurs autres aspects d’un système de stockage distribué : nous utilisons un modèle de files d’attente pour calculer le temps de réparation pour un système avec bande passante limitée ; nous étudions un système de codage hybride : en mixant les codes d’effacement avec la simple réplication des données ; enfin, nous étudions l’impact des différentes façons de distribuer des fragments de données entre les pairs
This thesis aims at providing tools to analyze and predict the performance of general large scale data storage systems. We use these tools to analyze the impact of different choices of system design on different performance metrics. For instance, the bandwidth consumption, the storage space overhead, and the probability of data loss should be as small as possible. Different techniques are studied and applied. First, we describe a simple Markov chain model that harnesses the dynamics of a storage system under the effects of peer failures and of data repair. Then we provide closed-form formulas that give good approximations of the model. These formulas allow us to understand the interactions between the system parameters. Indeed, a lazy repair mechanism is studied and we describe how to tune the system parameters to obtain an efficient utilization of bandwidth. We confirm by comparing to simulations that this model gives correct approximations of the system average behavior, but it does not capture its variations over time. We then propose a new stochastic model based on a fluid approximation that indeed captures the deviations around the mean behavior. These variations are most of the time neglected by previous works, despite being very important to correctly allocate the system resources. We additionally study several other aspects of a distributed storage system: we propose queuing models to calculate the repair time distribution under limited bandwidth scenarios; we discuss the trade-offs of a Hybrid coding (mixing erasure codes and replication); and finally we study the impact of different ways to distribute data fragments among peers, i. E. , placement strategies

APA, Harvard, Vancouver, ISO, and other styles

26

Chaintreau, Augustin. "Processus d'interaction dans les réseaux de données." Paris 6, 2006. http://www.theses.fr/2006PA066601.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Barré, Chloé. "Physique statistique des phénomènes de blocage dans les flux particulaires." Thesis, Paris 6, 2017. http://www.theses.fr/2017PA066227/document.

Full text

Abstract:

L'objectif de cette thèse porte sur l'étude des phénomènes de blocage dans un flux particules à faible densité dans un canal. Le blocage est induit par la géométrie du canal. L'essentiel de mes travaux concerne la description des situations où le blocage est contrôlé par les limites en capacité d'un canal. Le paramètre pertinent pour ce phénomène est donné par le nombre de particules minimum, N, conduisant à l'interruption du flux de particules. Un modèle stochastique simple introduit par Gabrielli et al. (PRL. 110, 170601, 2013) illustre ce comportement: des particules arrivent aléatoirement selon une distribution de Poisson à l'entrée d'un canal unidimensionnel et le traversent avec un temps constant, noté t. Le blocage survient lorsque N particules sont simultanément sur le pont. Le travail de cette thèse à été d'étudier les extensions de ce modèle. Les observables du système sont la probabilité de survie, le flux sortant ainsi que la statistique sur les particules sorties avant le blocage. Les différentes études ont permis pour le cas N>2, pour une distribution homogène quelconque et inhomogène d'entrée, pour un système de multi-canaux ainsi que pour une durée finie de blocage d'obtenir des résultats analytiques exactes ainsi que des approximations à l'aide d'outils statistique. Le dernier projet de cette thèse porte sur l'étude microscopique des phénomènes de blocage. Le modèle simple que nous avons étudié est un système bidimensionnel de particules browniennes soumis à une force de traînée et se déplaçant dans un canal avec rétrécissement. La présence d'un obstacle au milieu du canal peut causer un colmatage selon les valeurs des différents paramètres du système
This manuscript presents a study of blocking phenomenon in particulate streams flowing through anarrow channel. In particular, it examines situations in which blocking is controlled by the limitedcarrying capacity of the channel. It builds on a simple stochastic model, introduced by Gabrielli etal. (Phys. Rev. Lett. 110, 170601, 2013), in which particles arrive randomly according to a Poissondistribution at the entrance of a one-dimensional channel with an intensity λ and, unless interrupted,exit after a transit time, τ. Blocking occurs instantaneously when N=2 particles are simultaneouslypresent in the channel. The quantities of interest include the probability that the channel is still openat time t (survival probability) and the flux and total number of exiting particles. The thesisexamines a number of generalizations including when more than two particles must be present toinduce blockage, N>2, a time dependent intensity, a finite blocking time, and multi-channelsystems. We obtain exact and approximate analytical results using tools such as the masterequations describing the evolution of the n-particle partial probabilities, large deviation theory andqueuing theory. The theoretical results are validated by comparison with the results of numericalsimulations. The final chapter of the thesis uses a different approach, namely a brownian dynamics simulation of a two dimensional system of soft particles subjected to an external driving and dragforces. The presence of an obstacle in the middle of the channel can cause irreversible orintermittent clogging depending on the system geometry, temperature and particle stiffness

APA, Harvard, Vancouver, ISO, and other styles

28

Thompson, Guilherme. "Stochastic models for resource allocation in large distributed systems." Thesis, Paris 6, 2017. http://www.theses.fr/2017PA066539/document.

Full text

Abstract:

Cette thèse traite de quatre problèmes dans le contexte des grands systèmes distribués. Ce travail est motivé par les questions soulevées par l'expansion du Cloud Computing et des technologies associées. Le présent travail étudie l'efficacité de différents algorithmes d'allocation de ressources dans ce cadre. Les méthodes utilisées impliquent une analyse mathématique de plusieurs modèles stochastiques associés à ces réseaux. Le chapitre 1 fournit une introduction au sujet, ainsi qu'une présentation des principaux outils mathématiques utilisés dans les chapitres suivants. Le chapitre 2 présente un mécanisme de contrôle de congestion dans les services de Video on Demand fournissant des fichiers encodés dans diverses résolutions. On propose une politique selon laquelle le serveur ne livre la vidéo qu'à un débit minimal lorsque le taux d'occupation du serveur est supérieur à un certain seuil. La performance du système dans le cadre de cette politique est ensuite évaluée en fonction des taux de rejet et de dégradation. Les chapitres 3, 4 et 5 explorent les problèmes liés aux schémas de coopération entre centres de données (CD) situés à la périphérie du réseau. Dans le premier cas, on analyse une politique dans le contexte des services de cloud multi-ressources. Dans le second cas, les demandes arrivant à un CD encombré sont transmises à un CD voisin avec une probabilité donnée. Au troisième, les requêtes bloquées dans un CD sont transmises systématiquement à une autre où une politique de réservation (trunk) est introduite tel qu'une requête redirigée est acceptée seulement s'il y a un certain nombre minimum de serveurs libres dans ce CD
This PhD thesis investigates four problems in the context of Large Distributed Systems. This work is motivated by the questions arising with the expansion of Cloud Computing and related technologies. The present work investigates the efficiency of different resource allocation algorithms in this framework. The methods used involve a mathematical analysis of several stochastic models associated to these networks. Chapter 1 provides an introduction to the subject in general, as well as a presentation of the main mathematical tools used throughout the subsequent chapters. Chapter 2 presents a congestion control mechanism in Video on Demand services delivering files encoded in various resolutions. We propose a policy under which the server delivers the video only at minimal bit rate when the occupancy rate of the server is above a certain threshold. The performance of the system under this policy is then evaluated based on both the rejection and degradation rates. Chapters 3, 4 and 5 explore problems related to cooperation schemes between data centres on the edge of the network. In the first setting, we analyse a policy in the context of multi-resource cloud services. In second case, requests that arrive at a congested data centre are forwarded to a neighbouring data centre with some given probability. In the third case, requests blocked at one data centre are forwarded systematically to another where a trunk reservation policy is introduced such that a redirected request is accepted only if there are a certain minimum number of free servers at this data centre

APA, Harvard, Vancouver, ISO, and other styles

29

Larrañaga, Maialen. "Dynamic control of stochastic and fluid resource-sharing systems." Thesis, Toulouse, INPT, 2015. http://www.theses.fr/2015INPT0075/document.

Full text

Abstract:

Dans cette thèse, nous étudions le contrôle dynamique des systèmes de partage de ressources qui se posent dans divers domaines : réseaux de gestion des stocks, services de santé, réseaux de communication, etc. Nous visons à allouer efficacement les ressources disponibles entre des projets concurrents, selon certains critères de performance. Ce type de problème est de nature stochastique et peut être très complexe à résoudre. Nous nous concentrons donc sur le développement de méthodes heuristiques performantes. Dans la partie I, nous nous plaçons dans le cadre des Restless Bandit Problems, qui est une classe générale de problèmes d’optimisation dynamique stochastique. Relaxer la contrainte de trajectoire dans le problème d’optimisation permet de définir une politique d’index comme heuristique pour le modèle contraint d’origine, aussi appelée politique d’index de Whittle. Nous dérivons une expression analytique pour l’index de Whittle en fonction des probabilités stationnaires de l’état dans le cas où les bandits (ou projets) suivent un processus de naissance et de mort. D’une part, cette expression nécessite la vérification de plusieurs conditions techniques, d’autre part elle ne peut être calculée explicitement que dans certains cas spécifiques. Nous prouvons ensuite, que dans le cas particulier d’une file d’attente multi-classe avec abandon, la politique d’index de Whittle est asymptotiquement optimale aussi bien pour les régimes à faible trafic comme pour ceux à fort trafic. Dans la partie II, nous dérivons des heuristiques issues de l’approximation des systèmes stochastiques de partage de ressources par des modèles fluides déterministes. Nous formulons dans un premier temps une version fluide du problème d’optimisation relaxé que nous avons introduit dans la partie I, et développons une politique d’index fluide. L’index fluide peut toujours être calculé explicitement et surmonte donc les questions techniques qui se posent lors du calcul de l’index de Whittle. Nous appliquons les politiques d’index de Whittle et de l’index fluide à plusieurs cas : les fermes de serveurs éco-conscients, l’ordonnancement opportuniste dans les systèmes sans fil, et la gestion de stockage de produits périssables. Nous montrons numériquement que ces politiques d’index sont presque optimales. Dans un second temps, nous étudions l’ordonnancement optimal de la version fluide d’une file d’attente multi-classe avec abandon. Nous obtenons le contrôle optimal du modèle fluide en présence de deux classes de clients en concurrence pour une même ressource. En nous appuyant sur ces derniers résultats, nous proposons une heuristique pour le cas général de plusieurs classes. Cette heuristique montre une performance quasi-optimale lorsqu’elle est appliquée au modèle stochastique original pour des charges de travail élevées. Enfin, dans la partie III, nous étudions les phénomènes d’abandon dans le contexte d’un problème de distribution de contenu. Nous caractérisons une politique optimale de regroupement afin que des demandes issues d’utilisateurs impatients puissent être servies efficacement en mode diffusion
In this thesis we study the dynamic control of resource-sharing systems that arise in various domains: e.g. inventory management, healthcare and communication networks. We aim at efficiently allocating the available resources among competing projects according to a certain performance criteria. These type of problems have a stochastic nature and may be very complex to solve. We therefore focus on developing well-performing heuristics. In Part I, we consider the framework of Restless Bandit Problems, which is a general class of dynamic stochastic optimization problems. Relaxing the sample-path constraint in the optimization problem enables to define an index-based heuristic for the original constrained model, the so-called Whittle index policy. We derive a closed-form expression for the Whittle index as a function of the steady-state probabilities for the case in which bandits (projects) evolve in a birth-and-death fashion. This expression requires several technical conditions to be verified, and in addition, it can only be computed explicitly in specific cases. In the particular case of a multi-class abandonment queue, we further prove that the Whittle index policy is asymptotically optimal in the light-traffic and heavy-traffic regimes. In Part II, we derive heuristics by approximating the stochastic resource-sharing systems with deterministic fluid models. We first formulate a fluid version of the relaxed optimization problem introduced in Part I, and we develop a fluid index policy. The fluid index can always be computed explicitly and hence overcomes the technical issues that arise when calculating the Whittle index. We apply the Whittle index and the fluid index policies to several systems: e.g. power-aware server-farms, opportunistic scheduling in wireless systems, and make-to-stock problems with perishable items. We show numerically that both index policies are nearly optimal. Secondly, we study the optimal scheduling control for the fluid version of a multi-class abandonment queue. We derive the fluid optimal control when there are two classes of customers competing for a single resource. Based on the insights provided by this result we build a heuristic for the general multi-class setting. This heuristic shows near-optimal performance when applied to the original stochastic model for high workloads. In Part III, we further investigate the abandonment phenomena in the context of a content delivery problem. We characterize an optimal grouping policy so that requests, which are impatient, are efficiently transmitted in a multi-cast mode

APA, Harvard, Vancouver, ISO, and other styles

30

Al, Hanbali Ahmad Altman Eitan Nain Philippe. "Évaluation des performances des réseaux sans-fil mobiles." [S.l.] : [s.n.], 2006. http://www-sop.inria.fr/dias/Theses/phd-218.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Arda, Yasemin. "Politiques d’approvisionnement dans les systèmes à plusieurs fournisseurs et optimisation des décisions dans les chaînes logistiques décentralisées." Toulouse, INSA, 2008. http://eprint.insa-toulouse.fr/archive/00000208/.

Full text

Abstract:

La coordination des flux physiques au sein des chaînes logistiques est une tâche difficile à cause du caractère aléatoire des variations dues au marché et aux partenaires commerciaux et des antagonismes existants entre les objectifs économiques des partenaires. Les travaux développés dans cette thèse s’intègrent dans le cadre de pilotage de flux inter-organisationnelle dans les chaînes logistiques. Nous analysons deux approches ayant le but d’améliorer les performances des systèmes de production/stockage pilotés par des politiques de pilotage flux du type stock nominal. Dans la première approche, nous étudions les effets des stratégies multi-fournisseurs sur les performances des chaînes logistiques. Nous montrons que le délai moyen d’approvisionnement et les coûts moyens de stockage et de rupture de stock peuvent être réduits en optant pour une stratégie multi-fournisseurs. Dans la deuxième approche, nous analysons la dégradation de performances due à la décentralisation des décisions dans une chaîne logistique à deux niveaux en définissant un jeu de Stackelberg entre les partenaires. Nous proposons un contrat de coordination et montrons que le contrat proposé ramène les performances du système décentralisé vers les performances optimales du système centralisé

APA, Harvard, Vancouver, ISO, and other styles

32

Al, Hanbali Ahmad. "Évaluation des performances des réseaux sans-fil mobiles." Nice, 2006. http://www.theses.fr/2006NICE4058.

Full text

Abstract:

Cette thèse s'intéresse à l'impact de la mobilité sur les performances des réseaux ad hoc mobiles (MANETs en anglais). Elle comporte deux parties. La première partie de la thèse dresse un état-de-l'art du protocole TCP dans MANETs. La principale conclusion est que la mobilité dégrade les performances de TCP, à cause de problèmes de routage et de partitions du réseau qu'elle occasionne. Partant de ce constat, dans la deuxième partie de la thèse nous proposons et analysons des schémas de transmission qui s'appuient sur la mobilité. Plus précisément, chaque noeud peut servir de relais en l'absence de route directe entre la source et la destination. Nous nous sommes tout d'abord intéressés aux performances des nœuds relais (débit et taille moyenne des files) en utilisant le formalisme des files d'attente. Un des résultats principaux est que le débit des nœuds relais est minimisé quand les noeuds bougent selon des modèles de mouvements aléatoires qui ont une distribution stationnaire uniforme de position. Pour optimiser les performances du protocole de relais à deux sauts, particulièrement le délai de transmission, nous avons ensuite étudié le cas où un paquet peut avoir plusieurs copies dans le réseau, sous l'hypothèse où ces copies ont des durées de vie limitée. Les performances (délai, énergie consommée) ont été obtenues en utilisant le formalisme des chaînes de Markov absorbantes, ainsi que des modèles fluides. Nous avons appliqué nos résultats pour optimiser la consommation d'énergie en présence de contraintes sur les délais
This thesis deals with the mobility impact on the performance of mobile ad hoc network (MANET). It contains two parts. The first part surveys the TCP protocol over MANET. The main conclusion is that mobility degrades the TCP performance. Since it induces frequent route failures and extended network partitions. These implications were the motivation in the second part to introduce and evaluate new transmission schemes that rely on the mobility to improve the capacity of MANET. More precisely, in the absence of a direct route between two nodes the rest of the nodes in the network can serve as the relay nodes. In the beginning, the focus was on the performance of the relay nodes (throughput and relay buffer size) using a detailed queueing analysis. One of the main results was that random mobility models that have uniform stationary distribution of nodes location achieve the lowest throughput of relaying. Next, in order to optimize the performance of the two-hop relay protocol, especially the delivery delay of packets, we evaluated the multicopy extension under the assumption that the lifetime of the packets is limited. The performance results (delivery delay, round trip time, consumed energy) were derived using the theory of absorbing Markov chains and the fluid approximations. These results were exploited to optimize the total energy consumed subject to a constraint on the delivery delay

APA, Harvard, Vancouver, ISO, and other styles

33

Nya, Kamtchoum Narcisse. "Modèles multicellulaires pour les réseaux mobiles 4G." Electronic Thesis or Diss., Sorbonne université, 2018. http://www.theses.fr/2018SORUS079.

Full text

Abstract:

Afin de satisfaire le besoin toujours croissant en débit et offrir toujours plus de services, ce où que les utilisateurs se trouvent, les réseaux cellulaires évoluent rapidement vers des technologies caractérisées par une interface radio de plus en plus sophistiquée. Par exemple, alors que le déploiement des réseaux 4G ne faisaient que commencer, les premières mises à jour vers les solutions LTE-A étaient déjà planifiées par les opérateurs, et actuellement, les technologies 5G font l'objet de recherches actives à travers le monde. Ces changements rapides sont motivés par l'explosion du trafic mobile, comme le montrent des nombreuses études et observations sur les réseaux actuels. Ce trafic est principalement généré par des utilisateurs équipés de smartphones, tablettes, et autres équipements mobiles. Cependant, les réseaux actuels ont du mal à s'adapter à cette proportion toujours grandissante d'utilisateurs mobiles et à leur fournir un service adapté. Dans ce contexte, un des enjeux importants pour les opérateurs et équipementiers est de disposer d'outils efficaces pour évaluer les performances de leurs réseaux et mieux les dimensionner. Cette thèse porte donc sur le développement de modèles analytiques, à la fois précis et simples d'utilisation, permettant de répondre aux problèmes posés par l'évaluation de performances dans les réseaux cellulaires de nouvelle génération. Les modèles s'appuient sur la théorie des files d'attente et des processus stochastiques et permettent d'évaluer les performances d'un réseau et de ses utilisateurs en tenant compte de leur mobilité. Dans un premier temps, sont présentés tour à tour des modèles dédiés aux différents types de cellules rencontrées dans les réseaux cellulaires et aux utilisateurs qui visitent ces cellules. Dans un second temps, des modèles dédiés à un réseau cellulaire dans son ensemble sont présentés. Ces modèles réseaux combinent les précédents modèles dédiés aux cellules et un modèle de routage reproduisant le routage des utilisateurs mobiles entre les différentes cellules qui constituent le réseau. Tous les modèles proposés ont été pensés afin d'obtenir des expressions simples de l'ensemble des paramètres de performances du système. Cette simplicité associée à la rapidité de résolution rend possible les études de performance des systèmes les plus complexes, comme en témoignent les nombreux exemples inclus dans cette thèse
In order to meet the ever-increasing need for bandwidth and to offer ever more services, wherever users are, cellular networks are rapidly evolving towards technologies characterized by an increasingly sophisticated radio interface. For example, while the deployment of 4G networks was just beginning, operators already planned the first updates to LTE-A solutions and 5G technologies are currently receiving active attention. These rapid changes are motivated by the explosion of mobile traffic, as shown by numerous studies and observations on current networks. Users equipped with smartphones, tablets, and other mobile devices mainly generate this traffic. However most of models for cellular networks in literature do not take into account mobility of users. Authors who have tried to take into account users' mobility, propose models based on hypotheses like users moving with infinite speed. In this thesis we have developed analytical models for 4G and 5G cellular networks taking into account user mobility in a realistic way. The proposed models were designed to be simple and easy to solve, allowing users and networks performance to be evaluated almost instantaneously. Our first analysis and results where on the impact of mobility in dense LTE-A networks with small cells. We developed two models to access static users performance in small cell with mixed users (static and mobile users). The first model is based on Markov chains and the second one on Processor-Sharing queue. Our second analysis and results where on LTE/LTE-A macrocells with two coding zones and visited by mobile users. We proposed a model based on queuing theory to study the performance of mobile users in a LTE/LTE-A macrocell with different radio conditions over its coverage area. Then, we have then extended these models to the case of homogeneous cellular networks where cells are statistically identical. These models allowed us to show the positive impact of user mobility on performance in a cell or in a network. Moreover, we showed that this performance gain was not a monotonous function of user mobility, which is an important result showing the impact of hard handover implemented in LTE and LTE-A networks on performance. Finally, we turned our attention to heterogeneous networks with different type of cells and visited by users with different profiles (speed, amount of data to be transferred)

APA, Harvard, Vancouver, ISO, and other styles

34

Gayon, Jean-Philippe. "Commande optimale de systèmes de production par anticipation." Châtenay-Malabry, Ecole centrale de Paris, 2004. http://www.theses.fr/2004ECAP0957.

Full text

Abstract:

Les technologies de l'information offrent aux entreprises des possibilités croissantes pour piloter en temps réel leurs systèmes de production. Pour prendre ses décisions, le gestionnaire peut disposer d'informations telles que les niveaux des stocks, l'état de la production ou encore une information avancée sur la demande. Bien que les bénéfices liés à l'utilisation de ces informations soient intuitivement clairs, il est beaucoup moins évident de les utiliser concrètement pour prendre des décisions. Il existe un besoin réel de principes théoriques permettant d'assister les entreprises dans la définition de règles de gestion. Notre objectif est de contribuer à la définition de règles pour piloter en temps réel des systèmes de production par anticipation. Le chapitre 1 délimite le cadre de nos recherches. Le chapitre 2 présente un état de l'art et une classification des modèles de commande optimale de systèmes de production par anticipation à événements discrets stochastiques. Les chapitres 3, 4 et 5 étudient trois modèles originaux, respectivement sur l'allocation dynamique de stock avec une information sur l'état d'avancement de la production, sur l'allocation dynamique de stock avec une information avancée sur la demande et sur la gestion dynamique des prix dans un environnement économique fluctuant. Pour chacun des modèles, l'objectif est de déterminer la politique qui minimise les coûts actualisés ou moyens à horizon infini. Nous formulons ces problèmes comme des processus de décision markoviens et nous caractérisons la structure de la politique optimale. A partir de résultats numériques obtenus par itération sur la valeur, nous étudions, entre autres, l'influence de la variance du temps de production sur la performance, la valeur d'une information avancée sur la demande et le bénéfice lié à une gestion dynamique des prix.

APA, Harvard, Vancouver, ISO, and other styles

35

Da, Silva Soares Ana. "Fluid queues: building upon the analogy with QBD processes." Doctoral thesis, Universite Libre de Bruxelles, 2005. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/211053.

Full text

Abstract:

Les files d'attente fluides sont des processus markoviens à deux dimensions, où la première composante, appelée le niveau, représente le contenu d'un réservoir et prend des valeurs continues, et la deuxième composante, appelée la phase, est l'état d'un processus markovien dont l'évolution contrôle celle du niveau. Le niveau de la file fluide varie linéairement avec un taux qui dépend de la phase et qui peut prendre n'importe quelle valeur réelle.

Dans cette thèse, nous explorons le lien entre les files fluides et les processus QBD, et nous appliquons des arguments utilisés en théorie des processus de renouvellement pour obtenir la distribution stationnaire de plusieurs modèles fluides.

Nous commençons par l'étude d'une file fluide avec un réservoir de taille infinie; nous déterminons sa distribution stationnaire, et nous présentons un algorithme permettant de calculer cette distribution de manière très efficace. Nous observons que la distribution stationnaire de la file fluide de capacité infinie est très semblable à celle d'un processus QBD avec une infinité de niveaux. Nous poursuivons la recherche des similarités entre les files fluides et les processus QBD, et nous étudions ensuite la distribution stationnaire d'une file fluide de capacité finie. Nous montrons que l'algorithme valable pour le cas du réservoir infini permet de calculer toutes les quantités importantes du modèle avec un réservoir fini.

Nous considérons ensuite des modèles fluides plus complexes, de capacité finie ou infinie, où le comportement du processus markovien des phases peut changer lorsque le niveau du réservoir atteint certaines valeurs seuils. Nous montrons que les méthodes développées pour des modèles classiques s'étendent de manière naturelle à ces modèles plus complexes.

Pour terminer, nous étudions les conditions nécessaires et suffisantes qui mènent à l'indépendance du niveau et de la phase d'une file fluide de capacité infinie en régime stationnaire. Ces résultats s'appuient sur des résultats semblables concernant des processus QBD.

Markov modulated fluid queues are two-dimensional Markov processes, of which the first component, called the level, represents the content of a buffer or reservoir and takes real values; the second component, called the phase, is the state of a Markov process which controls the evolution of the level in the following manner: the level varies linearly at a rate which depends on the phase and which can take any real value.

In this thesis, we explore the link between fluid queues and Quasi Birth-and-Death (QBD) processes, and we apply Markov renewal techniques in order to derive the stationary distribution of various fluid models.

To begin with, we study a fluid queue with an infinite capacity buffer; we determine its stationary distribution and we present an algorithm which performs very efficiently in the determination of this distribution. We observe that the equilibrium distribution of the fluid queue is very similar to that of a QBD process with infinitely many levels. We further exploit the similarity between the two processes, and we determine the stationary distribution of a finite capacity fluid queue. We show that the algorithm available in the infinite case allows for the computation of all the important quantities entering in the expression of this distribution.

We then consider more complex models, of either finite or infinite capacities, in which the behaviour ff the phase process may change whenever the buffer is empty or full, or when it reaches certain thresholds. We show that the techniques that we develop for the simpler models can be extended quite naturally in this context.

Finally, we study the necessary and sufficient conditions that lead to the independence between the level and the phase of an infinite capacity fluid queue in the stationary regime. These results are based on similar developments for QBD processes.
Doctorat en sciences, Spécialisation mathématiques
info:eu-repo/semantics/nonPublished

APA, Harvard, Vancouver, ISO, and other styles

36

Smaili, Khaled. "Modélisation et optimisation des performances de systèmes de production." Toulouse 3, 1993. http://www.theses.fr/1993TOU30203.

Full text

Abstract:

Les systemes de production consideres dans cette these sont surtout des ateliers flexibles manufacturiers. Ils sont analyses en tant que systemes decisionnels a evenements discrets. Les outils de representation de tels systemes sont encore relativement peu nombreux. Il s'agit principalement des reseaux de files d'attente, des reseaux de petri et des processus de markov. L'objectif de la these, qui comporte quatre parties, est l'elaboration des modeles permettant l'evaluation et l'optimisation de performances de systemes de production. Le probleme de decision etudie dans cette these est celui de l'affectation en temps reel des taches a executer sur les machines disponibles. La modelisation d'ateliers flexibles fait l'objet de la premiere partie. L'atelier etant represente par un reseau de files d'attente multiclasse ouvert, le but de la deuxieme partie est l'optimisation du routage des produits. L'optimisation repose sur la determination des valeurs optimales de parametres de decision permettant de repartir de facon equilibree les flots de produits dans l'atelier. La troisieme partie est consacree a la recherche de politiques d'affectation dynamiques optimales. Le probleme d'affectation dynamique optimale est analyse par la theorie des processus de decision markovien. Enfin, la derniere partie de cette these propose des methodes analytiques permettant l'evaluation des politiques sous-optimales d'affectation dynamique

APA, Harvard, Vancouver, ISO, and other styles

37

Politaki, Dimitra. "Vers la modélisation de clusters de centres de données vertes." Thesis, Université Côte d'Azur (ComUE), 2019. http://www.theses.fr/2019AZUR4116.

Full text

Abstract:

La consommation énergétique des clusters de centres de données augmente rapidement, ce qui en fait les consommateurs d'électricité à la croissance la plus rapide au monde. Les sources d’électricité renouvelables et en particulier l’énergie solaire en tant qu’énergie propre et abondante peuvent être utilisées pour couvrir leurs besoins en électricité et les rendre «verts», c’est-à-dire alimentés par le photovoltaïque. Ce potentiel peut être exploré en prévoyant l'irradiance solaire et en évaluant la capacité fournie pour les clusters de centres de données. Dans cette thèse, nous développons des modèles stochastiques pour l'énergie solaire; un à la surface de la Terre et un second qui modélise le courant de sortie photovoltaïque. Nous d'abord validons nos modèles par des données réels, puis nous proposons une étude comparative avec d’autres systèmes, notamment les modèles dits on-off. Nous concluons que notre modèle d'irradiance solaire peut capturer les corrélations multi-échelles de façon plus optimale, et il se montre particulièrement convénient dans le cas d’une production à petite échelle. De plus, nous proposons une nouvelle analyse de cycle de vie pour un système de cluster réel, ainsi qu'un modèle de cluster prenant en charge la soumission de travaux par lots et prenant en compte le comportement client impatient et persistant. Enfin, pour comprendre les caractéristiques essentielles du cluster d’ordinateurs, nous analysons deux cas: le complexe Google publié et le Nef cluster de l’Inria. Nous avons également implémenté marmoteCore-Q, un outil de simulation d’une famille de modèles de file d’attente, basé sur nos modèles
Data center clusters energy consumption is rapidly increasing making them the fastest-growing consumers of electricity worldwide. Renewable electricity sources and especially solar energy as a clean and abundant energy can be used, in many locations, to cover their electricity needs and make them "green" namely fed by photovoltaics. This potential can be explored by predicting solar irradiance and assessing the capacity provision for data center clusters. In this thesis we develop stochastic models for solar energy; one at the surface of the Earth and a second one which models the photovoltaic output current. We then compare them to the state of the art on-off model and validate them against real data. We conclude that the solar irradiance model can better capture the multiscales correlations and is suitable for small scale cases. We then propose a new job life-cycle of a complex and real cluster system and a model for data center clusters that supports batch job submissions and cons iders both impatient and persistent customer behavior. To understand the essential computer cluster characteristics, we analyze in detail two different workload type traces; the first one is the published complex Google trace and the second, simpler one, which serves scientific purposes, is from the Nef cluster located at the research center Inria Sophia Antipolis. We then implement the marmoteCore-Q, a tool for the simulation of a family of queueing models based on our multi-server model for data center clusters with abandonments and resubmissions

APA, Harvard, Vancouver, ISO, and other styles

38

Excoffier, Mathilde. "Chance-Constrained Programming Approaches for Staffing and Shift-Scheduling Problems with Uncertain Forecasts : application to Call Centers." Thesis, Paris 11, 2015. http://www.theses.fr/2015PA112244/document.

Full text

Abstract:

Le problème de dimensionnement et planification d'agents en centre d'appels consiste à déterminer sur une période le nombre d'interlocuteurs requis afin d'atteindre la qualité de service exigée et minimiser les coûts induits. Ce sujet fait l'objet d'un intérêt croissant pour son intérêt théorique mais aussi pour l'impact applicatif qu'il peut avoir. Le but de cette thèse est d'établir des approches en contraintes en probabilités en considérant l'incertitude de la demande.Tout d'abord, la thèse présente un modèle en problème d'optimisation stochastique avec contrainte en probabilité jointe traitant la problématique complète en une étape afin d'obtenir un programme facile à résoudre. Une approche basée sur l'idée de continuité est proposée grâce à des lois de probabilité continues, une nouvelle relation entre les taux d'arrivées et les besoins théoriques et la linéarisation de contraintes. La répartition du risque global est faite pendant le processus d'optimisation, permettant une solution au coût réduit. Ces solutions résultantes respectent le niveau de risque tout en diminuant le coût par rapport à d'autres approches.De plus, le modèle en une étape est étendu pour améliorer sa représentation de la réalité. D'une part, le modèle de file d'attente est amélioré et inclus la patience limitée des clients. D'autre part, une nouvelle expression de l'incertitude est proposée pour prendre la dépendance des périodes en compte.Enfin, une nouvelle représentation de l'incertitude est considérée. L'approche distributionally robust permet de modéliser le problème sous l'hypothèse que la loi de probabilité adéquate est inconnue et fait partie d'un ensemble de lois, défini par une moyenne et une variance données. Le problème est modélisé par une contrainte en probabilité jointe. Le risque à chaque période est définie par une variable à optimiser.Un problème déterministe équivalent est proposé et des approximations linéaires permettent d'obtenir une formulation d'optimisation linéaire
The staffing and shift-scheduling problems in call centers consist in deciding how many agents handling the calls should be assigned to work during a given period in order to reach the required Quality of Service and minimize the costs. These problems are subject to a growing interest, both for their interesting theoritical formulation and their possible applicative effects. This thesis aims at proposing chance-constrained approaches considering uncertainty on demand forecasts.First, this thesis proposes a model solving the problems in one step through a joint chance-constrained stochastic program, providing a cost-reducing solution. A continuous-based approach leading to an easily-tractable optimization program is formulated with random variables following continuous distributions, a new continuous relation between arrival rates and theoritical real agent numbers and constraint linearizations. The global risk level is dynamically shared among the periods during the optimization process, providing reduced-cost solution. The resulting solutions respect the targeted risk level while reducing the cost compared to other approaches.Moreover, this model is extended so that it provides a better representation of real situations. First, the queuing system model is improved and consider the limited patience of customers. Second, another formulation of uncertainty is proposed so that the period correlation is considered.Finally, another uncertainty representation is proposed. The distributionally robust approach provides a formulation while assuming that the correct probability distribution is unknown and belongs to a set of possible distributions defined by given mean and variance. The problem is formulated with a joint chance constraint. The risk at each period is a decision variable to be optimized. A deterministic equivalent problem is proposed. An easily-tractable mixed-integer linear formulation is obtained through piecewise linearizations

APA, Harvard, Vancouver, ISO, and other styles

39

Ibrahim, Rita. "Utilisation des communications Device-to-Device pour améliorer l'efficacité des réseaux cellulaires." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLC002/document.

Full text

Abstract:

Cette thèse étudie les communications directes entre les mobiles, appelées communications D2D, en tant que technique prometteuse pour améliorer les futurs réseaux cellulaires. Cette technologie permet une communication directe entre deux terminaux mobiles sans passer par la station de base. La modélisation, l'évaluation et l'optimisation des différents aspects des communications D2D constituent les objectifs fondamentaux de cette thèse et sont réalisés principalement à l'aide des outils mathématiques suivants: la théorie des files d'attente, l'optimisation de Lyapunov et les processus de décision markovien partiellement observable POMDP. Les résultats de cette étude sont présentés en trois parties. Dans la première partie, nous étudions un schéma de sélection entre mode cellulaire et mode D2D. Nous dérivons les régions de stabilité des scénarios suivants: réseaux cellulaires purs et réseaux cellulaires où les communications D2D sont activées. Une comparaison entre ces deux scénarios conduit à l'élaboration d'un algorithme de sélection entre le mode cellulaire et le mode D2D qui permet d'améliorer la capacité du réseau. Dans la deuxième partie, nous développons un algorithme d'allocation de ressources des communications D2D. Les utilisateurs D2D sont en mesure d'estimer leur propre qualité de canal, cependant la station de base a besoin de recevoir des messages de signalisation pour acquérir cette information. Sur la base de cette connaissance disponibles au niveau des utilisateurs D2D, une approche d'allocation des ressources est proposée afin d'améliorer l'efficacité énergétique des communications D2D. La version distribuée de cet algorithme s'avère plus performante que celle centralisée. Dans le schéma distribué des collisions peuvent se produire durant la transmission de l'état des canaux D2D ; ainsi un algorithme de réduction des collisions est élaboré. En outre, la mise en œuvre des algorithmes centralisé et distribué dans un réseau cellulaire, type LTE, est décrite en détails. Dans la troisième partie, nous étudions une politique de sélection des relais D2D mobiles. La mobilité des relais représente un des principaux défis que rencontre toute stratégie de sélection de relais. Le problème est modélisé par un processus contraint de décision markovien partiellement observable qui prend en compte le dynamisme des relais et vise à trouver la politique de sélection de relais qui optimise la performance du réseau cellulaire sous des contraintes de coût
This thesis considers Device-to-Device (D2D) communications as a promising technique for enhancing future cellular networks. Modeling, evaluating and optimizing D2D features are the fundamental goals of this thesis and are mainly achieved using the following mathematical tools: queuing theory, Lyapunov optimization and Partially Observed Markov Decision Process (POMDP). The findings of this study are presented in three parts. In the first part, we investigate a D2D mode selection scheme. We derive the queuing stability regions of both scenarios: pure cellular networks and D2D-enabled cellular networks. Comparing both scenarios leads us to elaborate a D2D vs cellular mode selection design that improves the capacity of the network. In the second part, we develop a D2D resource allocation algorithm. We observe that D2D users are able to estimate their local Channel State Information (CSI), however the base station needs some signaling exchange to acquire this information. Based on the D2D users' knowledge of their local CSI, we provide an energy efficient resource allocation framework that shows how distributed scheduling outperforms centralized one. In the distributed approach, collisions may occur between the different CSI reporting; thus, we propose a collision reduction algorithm. Moreover, we give a detailed description on how both centralized and distributed algorithms can be implemented in practice. In the third part, we propose a mobile relay selection policy in a D2D relay-aided network. Relays' mobility appears as a crucial challenge for defining the strategy of selecting the optimal D2D relays. The problem is formulated as a constrained POMDP which captures the dynamism of the relays and aims to find the optimal relay selection policy that maximizes the performance of the network under cost constraints

APA, Harvard, Vancouver, ISO, and other styles

40

Da, Silva Veith Alexandre. "Quality of Service Aware Mechanisms for (Re)Configuring Data Stream Processing Applications on Highly Distributed Infrastructure." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSEN050/document.

Full text

Abstract:

Une grande partie de ces données volumineuses ont plus de valeur lorsqu'elles sont analysées rapidement, au fur et à mesure de leur génération. Dans plusieurs scénarios d'application émergents, tels que les villes intelligentes, la surveillance opérationnelle de grandes infrastructures et l'Internet des Objets (Internet of Things), des flux continus de données doivent être traités dans des délais très brefs. Dans plusieurs domaines, ce traitement est nécessaire pour détecter des modèles, identifier des défaillances et pour guider la prise de décision. Les données sont donc souvent rassemblées et analysées par des environnements logiciels conçus pour le traitement de flux continus de données. Ces environnements logiciels pour le traitement de flux de données déploient les applications sous-la forme d'un graphe orienté ou de dataflow. Un dataflow contient une ou plusieurs sources (i.e. capteurs, passerelles ou actionneurs); opérateurs qui effectuent des transformations sur les données (e.g., filtrage et agrégation); et des sinks (i.e., éviers qui consomment les requêtes ou stockent les données). Nous proposons dans cette thèse un ensemble de stratégies pour placer les opérateurs dans une infrastructure massivement distribuée cloud-edge en tenant compte des caractéristiques des ressources et des exigences des applications. En particulier, nous décomposons tout d'abord le graphe d'application en identifiant quelques comportements tels que des forks et des joints, puis nous le plaçons dynamiquement sur l'infrastructure. Des simulations et un prototype prenant en compte plusieurs paramètres d'application démontrent que notre approche peut réduire la latence de bout en bout de plus de 50% et aussi améliorer d'autres métriques de qualité de service. L'espace de recherche de solutions pour la reconfiguration des opérateurs peut être énorme en fonction du nombre d'opérateurs, de flux, de ressources et de liens réseau. De plus, il est important de minimiser le coût de la migration tout en améliorant la latence. Des travaux antérieurs, Reinforcement Learning (RL) et Monte-Carlo Tree Searh (MCTS) ont été utilisés pour résoudre les problèmes liés aux grands nombres d’actions et d’états de recherche. Nous modélisons le problème de reconfiguration d'applications sous la forme d'un processus de décision de Markov (MDP) et étudions l'utilisation des algorithmes RL et MCTS pour concevoir des plans de reconfiguration améliorant plusieurs métriques de qualité de service
A large part of this big data is most valuable when analysed quickly, as it is generated. Under several emerging application scenarios, such as in smart cities, operational monitoring of large infrastructure, and Internet of Things (IoT), continuous data streams must be processed under very short delays. In multiple domains, there is a need for processing data streams to detect patterns, identify failures, and gain insights. Data is often gathered and analysed by Data Stream Processing Engines (DSPEs).A DSPE commonly structures an application as a directed graph or dataflow. A dataflow has one or multiple sources (i.e., gateways or actuators); operators that perform transformations on the data (e.g., filtering); and sinks (i.e., queries that consume or store the data). Most complex operator transformations store information about previously received data as new data is streamed in. Also, a dataflow has stateless operators that consider only the current data. Traditionally, Data Stream Processing (DSP) applications were conceived to run in clusters of homogeneous resources or on the cloud. In a cloud deployment, the whole application is placed on a single cloud provider to benefit from virtually unlimited resources. This approach allows for elastic DSP applications with the ability to allocate additional resources or release idle capacity on demand during runtime to match the application requirements.We introduce a set of strategies to place operators onto cloud and edge while considering characteristics of resources and meeting the requirements of applications. In particular, we first decompose the application graph by identifying behaviours such as forks and joins, and then dynamically split the dataflow graph across edge and cloud. Comprehensive simulations and a real testbed considering multiple application settings demonstrate that our approach can improve the end-to-end latency in over 50% and even other QoS metrics. The solution search space for operator reassignment can be enormous depending on the number of operators, streams, resources and network links. Moreover, it is important to minimise the cost of migration while improving latency. Reinforcement Learning (RL) and Monte-Carlo Tree Search (MCTS) have been used to tackle problems with large search spaces and states, performing at human-level or better in games such as Go. We model the application reconfiguration problem as a Markov Decision Process (MDP) and investigate the use of RL and MCTS algorithms to devise reconfiguring plans that improve QoS metrics

APA, Harvard, Vancouver, ISO, and other styles

41

Georgiadis, Stylianos. "Estimation des systèmes semi-markoviens à temps discret avec applications." Thesis, Compiègne, 2013. http://www.theses.fr/2013COMP2112/document.

Full text

Abstract:

Le présent travail porte sur l’estimation d’un système en temps discret dont l’évolution est décrite par une chaîne semi-markovienne (CSM) d’espace d’état fini. Nous présentons le principe d’invariance sous forme multidimensionnelle pour le noyau semi-markovien (NSM), ainsi que diverses mesures du processus. Ensuite, nous étudions l’estimation non-paramétrique de la loi stationnaire de la CSM, en considérant deux estimateurs différents, et nous montrons qu’ils ont le même comportement asymptotique. La probabilité de la première entrée est également introduite. Nous proposons un estimateur et nous étudions ses propriétés asymptotiques : la convergence forte et la normalité asymptotique.D’autre part, nous nous concentrons sur l’étude de la fiabilité des systèmes semi-markoviens. Nous définissons la fiabilité sur intervalle d’un système dont la fiabilité et la disponibilité sont des cas particuliers et nous étudions les propriétés asymptotiques d’un estimateur proposé. De plus, nous présentons une comparaison de l’estimation des différentes mesures de fiabilité fondées sur deux estimateurs du NSM, en réalisant une trajectoire unique et des observations multiples indépendantes. Ce travail fournit aussi des résultats dans le cas semi-markovien à temps discret avec espace d’état général. Nous évaluons l’approximation de moyenne et de diffusion des chaînes de renouvellement markovien. Enfin, nous nous sommes aussi intéressés à une autre classe des processus pour laquelle nous obtenons des résultats dans le cadre des files d’attente. Nous étudions l’approximation de moyenne pour le modèle d’Engset en temps continu et nous appliquons ce résultat aux files d’attente avec ré-essais
The present work concerns the estimation of a discrete-time system whose evolution is governed by a semi-Markov chain (SMC) with finitely many states. We present the invariance principle in a multidimensional form for the semi-Markov kernel (SMK) and some associated measures of the process. Afterwards, we study the nonparametric estimation of the stationary distribution of the SMC, considering two different estimators, and we prove that they hold the same asymptotic behavior. We introduce also the first hitting probability. We propose an estimator and study its asymptotic properties : the strong consistency and the asymptotic normality. On the other hand, we focus on the study of the dependability of semi-Markovsystems. We introduce the interval reliability whose special cases are the reliability and the availability measures and we study the asymptotic properties of a proposed estimator. Moreover, we present a comparison of nonparametric estimation for various reliability measures based on two estimators of the SMK, realizing a unique trajectory and multiple independent observations.Furthermore, this work provides results on the discrete-time semi-Markov case with general state space. We evaluate the average and diffusion approximation of Markov renewal chains. Finally, we are also interested in another class of processes for which we obtain results in the framework of queueing systems. We establish the average approximationfor the Engset model in continuous time and we apply this result to retrial queues

APA, Harvard, Vancouver, ISO, and other styles

42

Ait, Salaht Farah. "Chaînes de Markov Incomplètement spécifiées : analyse par comparaison stochastique et application à l'évaluation de performance des réseaux." Thesis, Versailles-St Quentin en Yvelines, 2014. http://www.theses.fr/2014VERS0018.

Full text

Abstract:

Dans cette thèse, nous étudions les problèmes d'incertitudes dans les modèles probabilistes et tentons de déterminer leur impact sur l'analyse de performances et le dimensionnement des systèmes. Nous considérons deux aspects du problème d'imprécision. Le premier, consiste à étudier des chaînes en temps discret dont les probabilités ou taux de transition ne sont pas parfaitement connus. Nous construisons de nouveaux algorithmes de calcul de bornes par éléments sur les vecteurs de distribution stationnaires de chaînes partiellement spécifiées. Ces algorithmes permettent de déterminer des bornes par élément à chaque étape de calcul. Le second aspect étudié concerne le problème de mesures de traces de trafic réelles dans les réseaux. Souvent très volumineuses, la modélisation des traces de trafic est généralement impossible à effectuer de façon suffisamment précise et l'adéquation avec une loi de probabilité connue n'est pas assez réaliste. Utilisant une description par histogramme du trafic, nous proposons d'appliquer une nouvelle méthode d’évaluation de performance des réseaux. Fondée sur la comparaison stochastique pour construire des bornes optimales de supports réduits des histogrammes de trafics et sur la notion de monotonie stochastique des éléments de réseau, cette méthode permet de définir, de manière très pertinente, des garanties sur les mesures de performance. Nous obtenons en effet des bornes stochastiques supérieures et inférieures sur la longueur du tampon, les pertes, etc. L'intérêt et l'impact de notre méthode sont présentés sur diverses applications : éléments de réseau, AQM, réseaux de files d'attente, file avec processus d'arrivée non-stationnaire, etc
This thesis is devoted to the uncertainty in probabilistic models, how it impacts their analysis and how to apply these methods to performance analysis and network dimensioning. We consider two aspects of the uncertainty. The first consists to study a partially specified Markov chains. The missing of some transitions in the exact system because of its complexity can be solved by constructing bounding systems where worst-case transitions are defined to obtain an upper or a lower bound on the performance measures. We propose to develop new algorithms which give element-wise bounds of the steady-state distribution for the partially specified Markov chain. These algorithms are faster than the existing ones and allow us to compute element-wise bounds at each iteration.The second aspect studied concerns the problem of the measurements of real traffic trace in networks. Exact analysis of queueing networks under real traffic becomes quickly intractable due to the state explosion. Assuming the stationarity of flows, we propose to apply the stochastic comparison method to derive performance measure bounds under histogram-based traffics. We apply an algorithm based on dynamic programming to derive optimal bounding traffic histograms on reduced state spaces. Using the stochastic bound histograms and the monotonicity of the networking elements, we show how we can obtain, in a very efficient manner, guarantees on performance measures. We indeed obtain stochastic upper and lower bounds on buffer occupancy, losses, etc. The interest and the impact of our method are shown on various applications: elements of networks, AQM, queueing networks and queue with non-stationary arrival process

APA, Harvard, Vancouver, ISO, and other styles

43

Alfonso, Lizarazo Edgar. "Optimization of blood collection systems : Balancing service quality given to the donor and the efficiency in the collection planning." Thesis, Saint-Etienne, EMSE, 2013. http://www.theses.fr/2013EMSE0698/document.

Full text

Abstract:

Les rapports d’activité de l’Établissement Français du Sang (EFS) font état d’une demande croissante de produits sanguins labiles (PSL) tels les concentrés globules rouges (CGR), les plaquettes, et le plasma. Afin d’assurer la demande vitale en PSL, il est primordial d’optimiser la logistique liée aux activités de collecte du sang et de ses composants. Pour faire face à cette situation, l’EFS Auvergne-Loire mène une réflexion dans le but d’utiliser de manière plus efficiente les dispositifs de collecte en sites fixes et mobiles pour améliorer (i) la qualité de service rendue au donneur, et (ii) l’efficience de l’utilisation des ressources humaines. Dans ce contexte nous avons développé dans cette thèse des outils opérationnels pour (i) la modélisation des dispositifs de collecte, (ii) la régulation des flux de donneurs, et (iii) la planification de collectes mobiles.La méthode d'analyse des dispositifs de collecte est basée sur des techniques de simulation à événements discrets. Une modélisation préalable des flux de donneurs dans les systèmes de collecte en sites fixes et mobiles à l’aide de réseaux de Petri a été proposée. Pour la régulation de flux de donneurs, notamment pour la planification optimale des rendez-vous des donneurs et la planification de la capacité dans les systèmes de collecte au site fixe, deux approches ont été abordées: (a) Construction d'un algorithme basée sur techniques d'optimisation stochastique via simulation ; (b) Programmation mathématique: Modèle de programmation en nombres entiers non-linéaire (MINLP) basée sur réseaux de files d'attente et représentation et évaluation des systèmes à événements discrets à travers de programmation mathématique. Pour la planification de collectes mobiles. Deux types de modèles ont été développés : (a) Au niveau tactique : Modèles de programmation en nombres entiers linéaire (MIP) pour planifier les semaines de collectes pour chaque ensemble disponible sur un horizon de temps pour garantir l'autosuffisance à niveau régional des CGR. (b) Au niveau opérationnel : Modèle de programmation en nombres entiers linéaire (MIP) pour l’organisation du travail des équipes en charge de la collecte
Activity reports of the French Blood Establishment (EFS) indicate a growing demand for Labile Blood Products (LBP) as red blood cells (RBC), platelets and plasma. To ensure the vital demand of labile blood products (LBP), it’s essential to optimize the logistics related with the collection of blood components. To deal with this situation, the EFS Auvergne-Loire carry out a reflection in order to use more efficiently the collection devices in fixed and mobile sites, to improve the quality of service offered to the donor and the efficiency of human resources. In this context we have developed in this thesis operational tools for (i) modeling of blood collection devices (ii) The regulation of flows donors (iii) Planning of bloodmobile collections.The method analysis of collection devices is based on techniques of discrete event simulation. A preliminary modeling of donors’ flow in fixed and mobile collection systems using Petri nets was conducted. For the regulation of flow of donors, i.e. the optimal capacity planning and appointment scheduling of blood collections, two approaches were considered: (a) Simulation based-optimization.(b) Mathematical Programming: Mixed integer nonlinear programming (MINLP) based on queuing networks and mathematical programming representation of discrete event systems. For planning of bloodmobile collections. Two models have been developed: (a) At the tactical level: Mixed integer linear programming (MIP) to determine the weeks in which the mobile collection must be organized in order to ensure the regional self-sufficiency of RBC. (b) At the operational level: Mixed integer linear programming (MIP) for the planning of human resources in charge of blood collections

APA, Harvard, Vancouver, ISO, and other styles

44

Beguin, Maryse Y. "Modèles markoviens de transfert de charge dans les réseaux informatiques." Phd thesis, 1997. http://tel.archives-ouvertes.fr/tel-00004914.

Full text

Abstract:

Cette thèse porte sur la modélisation et l'evaluation d'algorithmes de transfert de charge dans des systèmes parallèles et/ou distribués. Après une synthèse des différentes approches possibles du transfert de charge et des problèmes rencontres pour leurs mises en oeuvre et leurs évaluations quantitatives, nous développons plusieurs modèles basés sur une évolution markovienne de la configuration des charges de l'ensemble des processeurs. Les indices de performance étudiés afin de comparer les valeurs obtenues avec transfert et sans transfert sont la saturation mémoire, le débit du système, la charge de travail et le temps de réponse moyen. Dans les deux premiers modèles seuls deux sites se transfèrent des tâches, mais les temps de communication et de transfert sont modélisés. Des valeurs critiques concernant la pertinence ou non du transfert sont obtenues. Lorsque les temps de communication et de transfert sont négligés devant les temps de calculs, deux modèles sont étudies. Le premier permet d'évaluer un algorithme d'équilibrage de charge pour un nombre quelconque de sites homogènes totalement connectés, de capacité mémoire finie. Cette étude permet de prévoir le comportement de systèmes massivement parallèles et des bornes supérieures de bénéfices que l'on peut attendre d'un réel transfert sont explicitées. Le deuxième prend en compte l'architecture du réseau et l'algorithme induit un transfert dés que la différence de charge entre deux sites voisins excède un. Dans le cas de réseaux infinis dont la topologie est régulière, ce modèle est ergodique et converge à vitesse exponentielle vers son régime stationnaire. Des résultats de simulations sont présentés pour différentes architectures et comparés aux solutions des équations de champ moyen, qui donnent de très bonnes approximations dans la plupart des cas pour les quantités d'intérêt pratique. Enfin, l'incidence sur la valeur des indices de performance est étudiée et interprétée.

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Processus de Markovthéorie des files d'attente'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles