Pierre L. DOUILLET

PhD Thesis : A Study of Some Queuing Systems

Thèse de Doctorat Université Paris 6 : Etude de certains systèmes à file d'attente

Soutenue le 12 juin 1998 devant le Jury composé de :	Serge Fdida (président)	Erol Gelenbe (rapporteur)	Serge Brezinski (rapporteur)
Monique Becker (directeur de thèse)	Bernard Lemaire (examinateur)	Satish Tripathi (examinateur)	André-Luc Beylot (examinateur)

Abstract : A Study of Some Queuing Systems

The bandwith and the quality of service requested by the forthcomming multimedia applications are inducing new problems in modelling and simulating the actual systems. For example, an acute description of the response-time of an hard disk is not simple.

We compare various methods : direct simulation, known method of inverse transform and finally a specific method to inverse the Laplace image of the response time of a queuing system under Poison arrivals (Pollaczek-Khintchine formula).

Our method of inverse Laplace transform is appliable to spline functions. It uses iterated convolutions, requesting a formal representation of piecewise functions, at least in the first phases of the computation, allowing to delay the effects of the bad conditionnement of the problem.

This formal representation has been developed with the Maple language and allows the effective convolution of functions whose angular points are described by formal parameters carrying formal assumptions. The resulting method not only supports the comparison with usual methods but leads to exact bounds.

Since denial of service are rare events, we re-examine a method of simulation that we had proposed (CRAS 1993), and that was based on a repeated application of the well-known "importance sampling".

The even possibility of a variance reduction in the study of the chain of the repairman depends on an M/M/1 hypothesis. But we show that it subsists, in the M/GI/1 case, an imbedding property for the Markov chain of the repairman, allowing an acceleration of the simulation of that Markov chain.

In addition, the file M/D/1 constitutes, with the generalization of formal computation, a tractable model that can be used in a systematic manner, at least to understand the effects of an M/M/1 assumption, since that model leads to wrongly identify "time of service" with " residual service time", as well as "individual" mean with "temporal" mean.

Back

Résumé : Etude de certains systèmes à files d'attente

Cette thèse a été entreprise dans le cadre d'une étude portant sur l'architecture d'un serveur multimédia. Une modélisation fine du temps de réponse d'un disque dur conduit à inverser l'image Laplace du temps de réponse du système (formule de Pollaczek-Khintchine).

Nous utilisé diverses méthodes : simulation directe, utilisation de méthodes connues de transformation inverse et enfin une méthode spécifique.

Notre méthode de transformation de Laplace inverse s'applique à des fonctions spline (polynomiales par morceaux, à support compact). Elle se fonde sur des calculs de convolutions itérées de la fonction image. Une représentation formelle est utilisée, au moins dans les premières phases du calcul, de façon à retarder les effets du mauvais conditionnement.

Cette représentation formelle a été développée en langage Maple et permet le calcul effectif de la convolution de fonctions dont les points anguleux sont décrits par des paramètres formels sur lesquels portent des clauses qualificatives (relations d'ordre formelles).

Cette méthode non seulement supporte la comparaison avec les méthodes usuelles mais conduit à un encadrement exact de la loi étudiée.

Les refus de service constituant des événements rares, nous réexaminons une méthode de simulation que nous avions proposée (CRAS 1993), et qui se fondait sur l'application itérative de la méthode "importance sampling". La possibilité même d'une réduction de variance pour l'étude de la chaîne du réparateur dépend de l'hypothèse que la file soit une file M/M/1.

Nous montrons qu'il subsiste néanmoins des propriétés d'emboîtement des matrices de Markov de la chaîne du réparateur lorsque la loi de service est quelconque, propriétés qu'il est possible d'utiliser pour accélérer la simulation de cette chaîne.

En outre, la file M/D/1 constitue, avec la généralisation des outils de calcul formel, un modèle assez aisément calculable pour pouvoir être utilisé de façon systématique. On sait en effet que la modélisation par M/M/1 conduit à confondre les notions de "temps de service" et de "temps de service résiduel", ainsi que les espérances "individuelle" et "temporelle".

Back

Remerciements

Je remercie d'abord le Professeur Monique Becker, de l'Institut National des Télécommunications (Evry) qui m'a proposé cette thèse quand je suivais les cours du DEA "Systèmes Informatique" de Paris 6, et qui a encadré mon travail de ses conseils et de son exemple pendant ces cinq années. Mener de front une thèse et un enseignement à plein temps en CPGE est une gageure qui n'eut pas été possible sans cette direction attentive et efficace.

Je remercie le Professeur Serge Fdida, de l'Université de Paris-6 (Laboratoire LIP6) d'avoir accepté de présider le jury de cette thèse, après avoir été l'un de mes professeurs.

Je remercie les Professeurs Claude Brezinski (Directeur du Laboratoire d'Analyse Numérique et d'Optimisation, Université de Lille-1) et Erol Gelenbe (Chairman du Departement d'Informatique, Université de Duke, USA) de m'avoir fait l'honneur d'être les rapporteurs de cette thèse. Leurs livres, puis leurs critiques et leurs conseils m'ont été précieux.

Je remercie les Professeurs Bernard Lemaire (Conservatoire des Arts et Métiers, Paris) et Satish Tripathi (College of Engeenering, University of California) d'avoir accepté de faire partie de ce jury et de m'avoir fait profiter de leur expérience.

Je remercie André-Luc Beylot, qui est actuellement au Lab. Prism (Versailles) après avoir été doctorant à l'INT, pour m'avoir montré la marche à suivre. La plupart des éléments de cette thèse ont été discutés pas à pas avec lui, et plusieurs points sont la continuation directe de ses travaux.

Je tiens également à remercier les Professeurs Troallic et Destobbeleer de l'Université du Havre, Quang de l'IUT de Paris, Vélu (Cnam), Vallée (Caen) pour ce qu'ils m'ont transmis et pour leurs encouragements à un moment ou à un autre de mon cursus.

Le présent travail a été grandement facilité par la compétence et la diligence des Bibliothécaires de Jussieu (en particulier en Mathématiques et en Physique) et de l'Université de Lille (en particulier en Mathématiques et en Informatique). J'ai le plus grand plaisir à le mentionner

Enfin, last but not least, ma compagne qui a pu se demander plus d'une fois pourquoi les "événements rares" revenaient aussi souvent dans notre vie commune...

Home  

Back