Soutenance de thèse: Farah Ait Salaht

Chaînes de Markov incomplètement spécifiées : analyse par comparaison stochastique et application à l'évaluation de performance des réseaux

Résumé : 

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.
 
Abstract :
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.

 Membres du jury :

Patrice MOREAUX, Professeur des Universités, à l’Université de Savoie/Laboratoire d'Informatique, Systèmes, Traitement de l'Information et de la Connaissance (LISTIC)- EA 3703- Annecy-le-Vieux - Rapporteur
Gerardo RUBINO, Directeur de Recherche, à l’INRIA/Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA) - UMR 6074 - Rennes - Rapporteur
Jean-Michel FOURNEAU, Professeur des Universités, à l’Université de Versailles Saint-Quentin-en-Yvelines/Laboratoire Parallélisme Réseaux Systèmes Modélisation (PRISM) - Versailles - Directeur de thèse
Hind CASTEL, Professeur, à l’Institut Télécom SudParis/Laboratoire Services répartis, Architectures, MOdélisation, Validation, Administration des Réseaux (SAMOVAR) - UMR 5157 - Evry - Examinateur
Nihal PEKERGIN, Professeur des Universités, à l’Université Paris-Est Créteil Val de Marne/Laboratoire d'Algorithmique, Complexité et Logique (LACL) - EA 4219 - Créteil - Examinateur
Véronique VEQUE, Professeur des Universités, à l’Université Paris Sud 11/Laboratoire des Signaux et Systèmes (L2S) - UMR 8506 CNRS - Examinateur 

 Imprimer  E-mail

Our website is protected by DMC Firewall!