Modélisation algébrique et évaluation de performances des mécanismes de gestion de la qualité de service dans les réseaux Ad hoc
Institution:
Toulouse 3Disciplines:
Directors:
Abstract EN:
Markov chains are often used for quantitative analysis of systems in many areas of application, and they are usually obtained by means of high level modeling formalism due to manual difficulty in specifying even a small system. Among widely used high level formalisms, we use stochastic process algebra. Unfortunately, restriction of temporal delay to memoryless distributions limits the application area of this framework, and leaves a lot of doubt around the precision of the results obtained by approximating distribution delay of all activities by Markovian one. This thesis proposes new methods and algorithms for enhancing the algebraic framework in order to make it able to specify and analyze real models. Methods and algorithms developed during this thesis are implemented, and numerical examples are presented to illustrate our contributions. We begin by introducing the concept of modeling with stochastic process algebras, and the widely used techniques to reduce and analyze the underlying transition diagram, as well as the novelties that we can bring to this formalism. Afterwards, we turn our attention to quality of service management mechanisms used in ad hoc network, like a new application area for formal design and modeling with algebraic formalism. After the identification of fundamental problems related to the dynamic characteristics of these kind of networks, we propose a new mechanism for providing end to end quality of service, then we realize functional and temporal analysis at the underlying transition diagram from the algebraic model, that we will use for the construction of a simulation model. Simulation results under various network loads show the ability of the proposed model to adapt with resources variations and the dynamic characteristics of ad hoc networks.
Abstract FR:
Les chaînes de Markov sont souvent utilisées pour l’analyse des performances des systèmes dans de nombreux domaines, et elles sont souvent obtenues par le biais d’un formalisme de modélisation de haut niveau. Parmi les formalismes couramment utilisés, on se place dans le cadre des algèbres de processus stochastiques. La restriction de la description temporelle aux distributions sans mémoire limite les domaines d’applications des algèbres de processus stochastiques, et laisse beaucoup de questions sur l’exactitude des valeurs des performances, obtenues par l’approximation des fonctions de distributions de délais de toutes les activités d’un système par des distributions Markoviennes. Cette thèse propose des méthodes et des algorithmes visant à optimiser le formalisme afin de pouvoir spécifier et évaluer les performances des modèles proches de la réalité. Les méthodes et les algorithmes développés au cours de cette thèse ont été implémentés, et des exemples numériques sont présentés pour illustrer les apports de cette thèse. Pour cela, nous introduisons tout d’abord le concept des algèbres de processus stochastiques, et les techniques d’analyses et d’agrégation utilisées, ainsi que les nouveautés qu’on peut ramener à ce formalisme. Ensuite, nous nous intéressons aux mécanismes de gestion de la qualité de service dans les réseaux ad hoc, comme nouveau domaine d’application. Après l’identification des questions fondamentales liées aux caractéristiques de ce type de réseaux, nous proposons un nouveau mécanisme de gestion de la qualité de service de bout en bout, puis nous réalisons une modélisation algébrique et des analyses qualitatives et quantitatives sur les diagrammes de transitions sous jacents du modèle algébrique, avant d’utiliser ce dernier pour la construction d’un modèle de simulation. Les analyses quantitatives réalisées sur le modèle de simulation sous différentes conditions, montrent la capacité du modèle proposé à s’adapter au dynamicité des ressources du réseau.